Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy

ABSTRACT

In the multicommodity rent-or-buy (MROB) network design problem we are given a network together with a set of k terminal pairs (s1, t1),.....,(sk, tk). The goal is to provision the network so that a given amount of low can be shipped between si and ti for all 1 ≤ i ≤ k simultaneously. In order to provision the network one can either rent capacity on edges at some cost per unit of ow, or buy them at some larger fixed cost. Bought edges have no incremental, ow-dependent cost. The overall objective is to minimize the total provisioning cost.Recently, Gupta et al. [8] presented a 12 approximation for the MROB problem. Their algorithm chooses a subset of the terminal pairs in the graph at random and then buys the edges of an approximate Steiner forest for these pairs. This technique has previously been introduced [9] for the single sink rent-or-buy network design problem.In this paper we give a 6.828-approximation for the MROB problem by refining the algorithm of Gupta et al. and simplifying their analysis. The improvement in our paper is based on a more careful adaptation and simplified analysis of the primal-dual algorithm for the Steiner forest problem due to Agrawal, Klein and Ravi [1]. Our result significantly reduces the gap between the single-sink [9] and multi-sink case.

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: 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
• 3: 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]
• 4: L. Becchetti, J. Könemann, S. Leonardi, and M. Pál. Sharing the cost more efficiently: Improved approximation for multicommodity rent-or-buy. See www.math.uwaterloo.ca/~jochen/docs/mrob-jv.pdf, 2004.
• 5: Joan Feigenbaum , Christos H. Papadimitriou , Scott Shenker, Sharing the cost of multicast transmissions, Journal of Computer and System Sciences, v.63 n.1, p.21-41, August 2001 [doi>10.1006/jcss.2001.1754]
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: 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]
• 8: 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
• 9: 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]
• 10: 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]
• 11: J. Könemann. Approximation Algorithms for Minimum-Cost Low-Degree Subgraphs. PhD thesis, Carnegie Mellon University, 2003.
• 12: J. Könemann and R. Ravi. Quasi-polynomial time approximation algorithm for low-degree minimum-cost steiner trees. In Proceedings of Foundations of Software Technology and Theoretical Computer Science., 2003.
• 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: 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