Moses Charikar
Adriana Karagiozova
ABSTRACT
We study the multicommodity buy-at-bulk network design problem in which we seek to design a network that satisfies the demands between terminals from a given set of source-sink pairs. The key characteristic of this problem is the fact that the cost functions associated with the edges of the graph are sub-additive monotone and hence experience economies of scale. In the non-uniform case, each edge has its own cost function -- possibly different from other edges. Special cases of this problem have been studied extensively: there are approximation algorithms when the edge cost functions are identical or when all source-sink pairs share the same source. We present the first non-trivial approximation algorithm for the general case. Our algorithm is an extremely simple randomized greedy algorithm and has an approximation guarantee of exp(O√ln n ln ln n)) when the instance has at most n source-sink pairs with unit demands. In the case of general demands, this yields an approximation factor of exp(O √ln N ln ln N)), where N is the sum of all demands.
- N. Alon, S. Hoory and N. Linial. The Moore bound for irregular graphs. In Graphs and Combinatorics 18, pages 53--57, 2002.Google Scholar
Cross Ref
- M. Andrews. Hardness of Buy-at-Bulk Network Design. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pages 115--124, 2004. Google ScholarDigital Library
- M. Andrews and L. Zhang. Bounds on Fiber Minimization in Optical Networks. In Proceedings of 2005 IEEE INFOCOM, 2005.Google Scholar
- B. Awerbuch, Y. Azar and Y. Bartal. On-line Generalized Steiner Problem. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 68--74, 1996. Google ScholarDigital Library
- B. Awerbuch and Y. Azar. Buy-At-Bulk Network Design. In Proceeding of the 38th Annual IEEE Symposium on Foundations of Computer Science, pages 542--547, 1997. Google ScholarDigital Library
- Y. Bartal. Probabilistic Approximation of Metric Spaces and its Algorithmic Applications. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, pages 184-193, 1996. Google ScholarDigital Library
- Y. Bartal. On Approximating Arbitrary Metrics by Tree Metrics. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 183--193, 1998. Google ScholarDigital Library
- C. Chekuri, S. Khanna and J. Naor. A deterministic algorithm for the cost-distance problem. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 232--233, 2001. Google ScholarDigital Library
- J. Fakcharoenphol, S. Rao and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 448--455, 2003. Google ScholarDigital Library
- S. Guha, A. Meyerson and K. Munagala. A constant factor approximation for the single sink edge installation problems. In Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing, pages 383--388, 2001. Google ScholarDigital Library
- A. Gupta, A. Kumar, M. Pàl and T. Roughgarden. Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pages 606--615, 2003. Google ScholarDigital Library
- A. Gupta, A. Kumar and T. Roughgarden. Simpler and better approximation algorithms for network design. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 365--372, 2003. Google ScholarDigital Library
- A. Kumar, A. Gupta and T. Roughgarden. A Constant Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 333--, 2002. Google ScholarDigital Library
- A. Meyerson. Online algorithms for network design. In Proceedings of the 16th ACM Symposium on Parallelism in Algorithms and Architectures, pages 275--280, 2004. Google ScholarDigital Library
- A. Meyerson, K. Munagala and S. Plotkin. Cost-Distance: Two-Metric Network Design. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, pages 624--630, 2000. Google ScholarDigital Library
- A. Meyerson, K. Munagala and S. Plotkin. Designing Networks Incrementally. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, pages 406--415, 2001. Google ScholarDigital Library
- S. Salman, J. Cheryian, R. Ravi, S. Subramanian. Buy-at-bulk network design: approximating the single-sink edge installation problem. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 619--628, 1997. Google ScholarDigital Library
- K. Talwar. Single-sink buy-at-bulk LP has constant integrality gap. In Proceedings of the 9th IPCO, LNCS vol 2337, pages 475--486, 2002. Google ScholarDigital Library
Index Terms
- On non-uniform multicommodity buy-at-bulk network design
Recommendations
Buy-at-Bulk Network Design with Protection
We consider approximation algorithms for buy-at-bulk network design, with the additional constraint that demand pairs be protected against a single edge or node failure in the network. In practice, the most popular model used in high-speed ...
Improved approximations for buy-at-bulk and shallow-light $$k$$k-Steiner trees and $$(k,2)$$(k,2)-subgraph
In this paper we give improved approximation algorithms for some network design problems. In the bounded-diameter or shallow-light $$k$$k-Steiner tree problem (SL$$k$$kST), we are given an undirected graph $$G=(V,E)$$G=(V,E) with terminals $$T\subseteq ...
A new approximation algorithm for the Selective Single-Sink Buy-at-Bulk problem in network design
The Selective Single-Sink Buy-at-Bulk problem was proposed by Awerbuch and Azar (FOCS 1997 ). For a long time, the only known non-trivial approach to approximate this problem is the tree-embedding method initiated by Bartal (FOCS 1996 ). In this paper, ...
Comments