Approximation via cost sharing: Simpler and better approximation algorithms for network design

ABSTRACT

We present constant-factor approximation algorithms for several widely-studied NP-hard optimization problems in network design, including the multicommodity rent-or-buy, virtual private network design, and single-sink buy-at-bulk problems. Our algorithms are simple and their approximation ratios improve over those previously known, in some cases by orders of magnitude.

We develop a general analysis framework to bound the approximation ratios of our algorithms. This framework is based on a novel connection between random sampling and game-theoretic cost sharing.

REFERENCES

• 1: Ajit Agrawal , Philip Klein , R. Ravi, When Trees Collide: An Approximation Algorithm for theGeneralized Steiner Problem on Networks, SIAM Journal on Computing, v.24 n.3, p.440-456, June 1995 [doi>10.1137/S0097539792236237]
• 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: Andrews, M., and Zhang, L. 2002. Approximation algorithms for access network design. Algorithmica 34, 2, 197--215. (Preliminary version in 39th FOCS, 1998).
• 4: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 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: Baruch Awerbuch , Yossi Azar , Yair Bartal, On-line generalized Steiner problem, Theoretical Computer Science, v.324 n.2-3, p.313-324, 20 September 2004 [doi>10.1016/j.tcs.2004.05.021]
• 7: Bartal, Y. 1994. Competitive analysis of distributed on-line problems---Distributed paging. Ph.D. dissertation, Tel-Aviv University, Tel-Aviv, Israel.
• 8: 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
• 9: 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]
• 10: On page migration and other relaxed task systems, Theoretical Computer Science, v.268 n.1, p.43-66, 10/06/2001 [doi>10.1016/S0304-3975(00)00259-0 ]
• 11: Yair Bartal , Amos Fiat , Yuval Rabani, Competitive algorithms for distributed data management, Journal of Computer and System Sciences, v.51 n.3, p.341-358, Dec. 1995 [doi>10.1006/jcss.1995.1073 ]
• 12: Luca Becchetti , Jochen Könemann , Stefano Leonardi , M. Pál, Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 13: Marshall Bern , Paul Plassmann, The steiner problem with edge lengths 1 and 2,, Information Processing Letters, v.32 n.4, p.171-176, Sept 1, 1989 [doi>10.1016/0020-0190(89)90039-2 ]
• 14: 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]
• 15: 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 (FOCS'06), p.677-686, October 21-24, 2006 [doi>10.1109/FOCS.2006.15]
• 16: 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
• 17: 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
• 18: Richard Cole , Ramesh Hariharan , Moshe Lewenstein , Ely Porat, A faster implementation of the Goemans-Williamson clustering algorithm, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.17-25, January 07-09, 2001, Washington, D.C., United States
• 19: N. G. Duffield , Pawan Goyal , Albert Greenberg , Partho Mishra , K. K. Ramakrishnan , Jacobus E. van der Merive, A flexible model for resource management in virtual private networks, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.95-108, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 20: Friedrich Eisenbrand , Fabrizio Grandoni, An improved approximation algorithm for virtual private network design, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 21: Eisenbrand, F., Grandoni, F., and Rothvoß, T. 2007. A tighter analysis of random sampling for connected facility location. Submitted.
• 22: Eisenbrand, F., Grandoni, G., Oriolo, G., and Skutella, M. 2005. New approaches for virtual private network design. In Proceedings of the 32nd Annual International Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science, vol. 3580. Springer-Verlag, New York, 1151--1162.
• 23: 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]
• 24: J. Andrew Fingerhut , Subhash Suri , Jonathan S. Turner, Designing least-cost nonblocking broadband networks, Journal of Algorithms, v.24 n.2, p.287-309, Aug. 1997 [doi>10.1006/jagm.1997.0866 ]
• 25: Lisa Fleischer , Jochen Könemann , Stefano Leonardi , Guido Schäfer, Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132609]
• 26: Gabow, H. N., Goemans, M. X., and Williamson, D. P. 1998. An efficient approximation algorithm for the survivable network design problem. Math. Prog. 82, 1-2, 13--40.
• 27: Goel, A., and Estrin, D. 2005. Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk. Algorithmica 43, 1-2, 5--15.
• 28: 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]
• 29: Michel X. Goemans , David P. Williamson, The primal-dual method for approximation algorithms and its application to network design problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 30: Grandoni, F., and Italiano, G. F. 2006. Improved approximation for single-sink buy-at-bulk. In Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC). 111--120.
• 31: S. Guha , A. Meyerson , K. Munagala, Hierarchical placement and network design problems, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.603, November 12-14, 2000
• 32: 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]
• 33: Anupam Gupta , Mohammad T. Hajiaghayi , Harald Räcke, Oblivious network design, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.970-979, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109665]
• 34: Anupam Gupta , Jon Kleinberg , Amit Kumar , Rajeev Rastogi , Bulent Yener, Provisioning a virtual private network: a network design problem for multicommodity flow, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.389-398, July 2001, Hersonissos, Greece [doi>10.1145/380752.380830]
• 35: 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
• 36: 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]
• 37: Gupta, A., and Pál, M. 2005. Stochastic Steiner trees without a root. In Proceedings of the 32nd Annual International Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science, vol. 3580. Springer-Verlag, New York, 1051--1063.
• 38: Anupam Gupta , Martin Pál , R. Ravi , Amitabh Sinha, Boosted sampling: approximation algorithms for stochastic optimization, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007419]
• 39: Gupta, A., Pál, M., Ravi, R., and Sinha, A. 2005. What about Wednesday? Approximation algorithms for multistage stochastic optimization. In Proceedings of the 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). Lecture Notes in Computer Science, vol. 3624. Springer-Verlag, New York, 86--98.
• 40: Gupta, A., Srinivasan, A., and Tardos, É. 2004b. Cost-sharing mechanisms for network design. In Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). Lecture Notes in Computer Science, vol. 3122. Springer-Verlag, New York, 139--150.
• 41: Hassin, R., Ravi, R., and Salman, F. S. 2004. Approximation algorithms for a capacitated network design problem. Algorithmica 38, 3, 417--431.
• 42: Ara Hayrapetyan , Chaitanya Swamy , Éva Tardos, Network design for information networks, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 43: Nicole Immorlica , David Karger , Maria Minkoff , Vahab S. Mirrokni, On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 44: Kamal Jain , Vijay Vazirani, Applications of approximation algorithms to cooperative games, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.364-372, July 2001, Hersonissos, Greece [doi>10.1145/380752.380825]
• 45: Kamal Jain , Vijay V. Vazirani, Equitable cost allocations via primal-dual-type algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509956]
• 46: D. R. Karget , M. Minkoff, Building Steiner trees with incomplete global knowledge, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.613, November 12-14, 2000
• 47: Samir Khuller , An Zhu, The general Steiner tree-star problem, Information Processing Letters, v.84 n.4, p.215-220, 30 November 2002 [doi>10.1016/S0020-0190(02)00271-5 ]
• 48: Kim, T. U., Lowe, T. J., Tamir, A., and Ward, J. E. 1996. On the location of a tree-shaped facility. Networks 28, 3, 167--175.
• 49: Philip N. Klein, A data structure for bicategories, with application to speeding up an approximation algorithm, Information Processing Letters, v.52 n.6, p.303-307, Dec. 23, 1994 [doi>10.1016/0020-0190(94)00156-1 ]
• 50: Jochen Könemann , Stefano Leonardi , Guido Schäfer, A group-strategyproof mechanism for Steiner forests, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 51: 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
• 52: Labbé, M., Laporte, G., Martín, I. M., and Salazar González, J. J. 2001. The median cycle problem. Tech. Rep. 2001/12, Department of Operations Research and Multicriteria Decision Aid at Université Libre de Bruxelles.
• 53: Lee, Y., Chiu, Y., and Ryan, J. 1996. A branch and cut algorithm for a Steiner tree-star problem. INFORMS J. Comput. 8, 3, 194--201.
• 54: 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
• 55: A. Meyerson, Designing Networks Incrementally, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.406, October 14-17, 2001
• 56: Pál, M. 2004. Cost sharing and approximation. Ph.D. dissertation, Cornell University.
• 57: Martin Pál , Éva Tardo, Group Strategyproof Mechanisms via Primal-Dual Algorithms, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.584, October 11-14, 2003
• 58: R. Ravi , F. S. Salman, Approximation Algorithms for the Traveling Purchaser Problem and its Variants in Network Design, Proceedings of the 7th Annual European Symposium on Algorithms, p.29-40, July 16-18, 1999
• 59: R. Ravi , Amitabh Sinha, Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems, Mathematical Programming: Series A and B, v.108 n.1, p.97-114, August 2006 [doi>10.1007/s10107-005-0673-5]
• 60: Gabriel Robins , Alexander Zelikovsky, Tighter Bounds for Graph Steiner Tree Approximation, SIAM Journal on Discrete Mathematics, v.19 n.1, p.122-134, 2005 [doi>10.1137/S0895480101393155]
• 61: 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]
• 62: Chaitanya Swamy , Amit Kumar, Primal–Dual Algorithms for Connected Facility Location Problems, Algorithmica, v.40 n.4, p.245-269, September 2004 [doi>10.1007/s00453-004-1112-3]
• 63: 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
• 64: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 65: Williamson, D. P., and van Zuylen, A. 2007. A simpler and better derandomization of an approximation algorithm for single-source rent-or-buy. Oper. Res. Lett. To appear.
• 66: Young, H. P. 1994. Cost allocation. In Handbook of Game Theory, R. J. Aumann and S. Hart, Eds. Vol. 2. North-Holland, Amsterdam, The Netherlands, Chap. 34, 1193--1235.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
Approximation algorithms, cost sharing, network design, random sampling