On non-uniform multicommodity buy-at-bulk network design

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.

REFERENCES

• 1: N. Alon, S. Hoory and N. Linial. The Moore bound for irregular graphs. In Graphs and Combinatorics 18, pages 53--57, 2002.
• 2: Matthew Andrews, Hardness of Buy-at-Bulk Network Design, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.115-124, October 17-19, 2004 [doi>10.1109/FOCS.2004.32]
• 3: M. Andrews and L. Zhang. Bounds on Fiber Minimization in Optical Networks. In Proceedings of 2005 IEEE INFOCOM, 2005.
• 4: Baruch Awerbuch , Yossi Azar , Yair Bartal, On-line generalized Steiner problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.68-74, January 28-30, 1996, Atlanta, Georgia, United States
• 5: B. Awerbuch , Y. Azar, Buy-at-bulk network design, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.542, October 19-22, 1997
• 6: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 7: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 8: Chandra Chekuri , Sanjeev Khanna , Joseph Naor, A deterministic algorithm for the cost-distance problem, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.232-233, January 07-09, 2001, Washington, D.C., United States
• 9: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780608]
• 10: Sudipto Guha , Adam Meyerson , Kamesh Munagala, A constant factor approximation for the single sink edge installation problems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.383-388, July 2001, Hersonissos, Greece [doi>10.1145/380752.380827]
• 11: Anupam Gupta , Amit Kumar , Martin Pál , Tim Roughgarden, Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.606, October 11-14, 2003
• 12: Anupam Gupta , Amit Kumar , Tim Roughgarden, Simpler and better approximation algorithms for network design, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780597]
• 13: Amit Kumar , Anupam Gupta , Tim Roughgarden, A Constant-Factor Approximation Algorithm for the Multicommodity, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.333, November 16-19, 2002
• 14: Adam Meyerson, Online algorithms for network design, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007958]
• 15: A. Meyerson , K. Munagala , S. Plotkin, Cost-distance: two metric network design, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.624, November 12-14, 2000
• 16: A. Meyerson, Designing Networks Incrementally, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.406, October 14-17, 2001
• 17: F. S. Salman , J. Cheriyan , R. Ravi , S. Subramanian, Buy-at-bulk network design: approximating the single-sink edge installation problem, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.619-628, January 05-07, 1997, New Orleans, Louisiana, United States
• 18: Kunal Talwar, The Single-Sink Buy-at-Bulk LP Has Constant Integrality Gap, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.475-486, May 27-29, 2002

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Design, Theory

Keywords:
approximation algorithms, buy-at-bulk, multicommodity, network design, non-uniform