Buy-at-bulk network design

被引：106

作者：

Awerbuch, B ^{[1
]}

Azar, Y ^{[1
]}

机构：

[1] Johns Hopkins Univ, Dept Comp Sci, Baltimore, MD 21218 USA

来源：

38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 1997年

关键词：

D O I：

10.1109/SFCS.1997.646143

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The essence of the simplest buy-at-bulk network design problem is buying network capacity "wholesale" to guarantee connectivity from all network nodes to a certain central network switch. Capacity a's sold with "volume discount": the more capacity a's bought, the cheaper is the price per unit of bandwidth. We provide O(log(2) n) randomized approximation algorithm for the problem. This solves the open problem in [15]. The only previously known solutions were restricted to special cases (Euclidean graphs) [15]. We solve additional natural variations of the problem, such as multi-sink: network design, as well as selective network design. These problems can be viewed as generalizations of the the Generalized Steiner Connectivity and Prize-collecting salesman (K-MST) problems. In the selective network design problem, some subset of k wells must be connected to the (single) refinery, so that the total cost is minimized.

引用

页码：542 / 547

页数：6