Approximation algorithms for node-weighted buy-at-bulk network design

ABSTRACT

We present algorithms with poly-logarithmic approximation ratios for the buy-at-bulk network design problem in the node-weighted setting. We obtain the following results where h is the number of pairs in the input.

• On O(log h) approximation for the single-sink non-uniform buy-at-bulk network design. Unless P = NP this ratio is tight up to constant factors.

• An O(log⁴ h) approximation for the multi-commodity non-uniform buy-at-bulk network design problem.

REFERENCES

• 1: Matthew Andrews, Hardness of Buy-at-Bulk Network Design, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.115-124, October 17-19, 2004 [doi>10.1109/FOCS.2004.32]
• 2: M. Andrews and L. Zhang. Approximation algorithms for access network design. Algorithmica, 34(2):197--215, 2002.
• 3: 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
• 4: 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
• 5: Moses Charikar , Adriana Karagiozova, On non-uniform multicommodity buy-at-bulk network design, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060617]
• 6: C. Chekuri , M. T. Hajiaghayi , G. Kortsarz , M. R. Salavatipour, Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.677-686, October 21-24, 2006 [doi>10.1109/FOCS.2006.15]
• 7: Chandra Chekuri , Sanjeev Khanna , Joseph (Seffi) 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
• 8: Chandra Chekuri , Sanjeev Khanna , F. Bruce Shepherd, Multicommodity flow, well-linked terminals, and routing problems, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060618]
• 9: Julia Chuzhoy , Anupam Gupta , Joseph (Seffi) Naor , Amitabh Sinha, On the approximability of some network design problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 10: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Journal of Computer and System Sciences, v.69 n.3, p.485-497, November 2004 [doi>10.1016/j.jcss.2004.04.011]
• 11: Uriel Feige , MohammadTaghi Hajiaghayi , James R. Lee, Improved approximation algorithms for minimum-weight vertex separators, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060674]
• 12: Lisa Fleischer , Kamal Jain , David P. Williamson, Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems, Journal of Computer and System Sciences, v.72 n.5, p.838-867, August 2006 [doi>10.1016/j.jcss.2005.05.006]
• 13: Michel X. Goemans , David P. Williamson, A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, v.24 n.2, p.296-317, April 1995 [doi>10.1137/S0097539793242618]
• 14: Sudipto Guha , Samir Khuller, Improved methods for approximating node weighted Steiner trees and connected dominating sets, Information and Computation, v.150 n.1, p.57-74, April 10, 1999 [doi>10.1006/inco.1998.2754]
• 15: Sudipto Guha , Anna Moss , Joseph (Seffi) Naor , Baruch Schieber, Efficient recovery from power outage (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.574-582, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301406]
• 16: 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]
• 17: 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]
• 18: 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
• 19: Mohammad T. Hajiaghayi , Robert D. Kleinberg , Tom Leighton , Harald Räcke, Oblivious routing on node-capacitated and directed graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 20: M. T. Hajiaghayi, G. Kortsarz, and M. R. Salavatipour. Approximating buy-at-bulk and shallow-light k-steiner tree. Proc. of APPROX, Springer LNCS 4110, 153--163, 2006.
• 21: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 22: K. Jain. A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica, 21(1):39--60, 2001.
• 23: David S. Johnson. Approximation algorithms for combinatorial problems. J. Comput. System Sci., 9:256--278, 1974.
• 24: Philip Klein , R. Ravi, A nearly best-possible approximation algorithm for node-weighted Steiner trees, Journal of Algorithms, v.19 n.1, p.104-115, July 1995 [doi>10.1006/jagm.1995.1029]
• 25: 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
• 26: Anna Moss , Yuval Rabani, Approximation algorithms for constrained for constrained node weighted steiner tree problems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.373-382, July 2001, Hersonissos, Greece [doi>10.1145/380752.380826]
• 27: F. S. Salman , J. Cheriyan , R. Ravi , S. Subramanian, Approximating the Single-Sink Link-Installation Problem in Network Design, SIAM Journal on Optimization, v.11 n.3, p.595-610, 2000 [doi>10.1137/S1052623497321432]
• 28: A. Schrijver. Combinatorial optimization. Springer, 2003.
• 29: 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
• 30: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001