Anupam Gupta
Skip Abstract Section
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.
- Agrawal, A., Klein, P., and Ravi, R. 1995. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput. 24, 3, 440--456. (Preliminary version in 23rd STOC, 1991). Google Scholar
Digital Library
- Andrews, M. 2004. Hardness of buy-at-bulk network design. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 115--124. Google ScholarDigital Library
- Andrews, M., and Zhang, L. 2002. Approximation algorithms for access network design. Algorithmica 34, 2, 197--215. (Preliminary version in 39th FOCS, 1998).Google ScholarDigital Library
- Arora, S., Lund, C., Motwani, R., Sudan, M., and Szegedy, M. 1998. Proof verification and the hardness of approximation problems. J. ACM 45, 3, 501--555. Google ScholarDigital Library
- Awerbuch, B., and Azar, Y. 1997. Buy-at-bulk network design. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 542--547. Google ScholarDigital Library
- Awerbuch, B., Azar, Y., and Bartal, Y. 2004. On-line generalized Steiner problem. Theoretical Computer Science 324, 2-3, 313--324. Google ScholarDigital Library
- Bartal, Y. 1994. Competitive analysis of distributed on-line problems---Distributed paging. Ph.D. dissertation, Tel-Aviv University, Tel-Aviv, Israel.Google Scholar
- Bartal, Y. 1996. Probabilistic approximations of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 184--193. Google ScholarDigital Library
- Bartal, Y. 1998. On approximating arbitrary metrics by tree metrics. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC). ACM, New York, 161--168. Google ScholarDigital Library
- Bartal, Y., Charikar, M., and Indyk, P. 2001. On page migration and other relaxed task systems. Theoret. Comput. Sci. 268, 1, 43--66. Google ScholarDigital Library
- Bartal, Y., Fiat, A., and Rabani, Y. 1995. Competitive algorithms for distributed data management. J. Comput. Syst. Sci. 51, 3, 341--358. (Preliminary version in 24th STOC, 1992). Google ScholarDigital Library
- Becchetti, L., Könemann, J., Leonardi, S., and Pál, M. 2005. Sharing the cost more efficiently: Improved approximation for multicommodity rent-or-buy. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 375--384. Google ScholarDigital Library
- Bern, M., and Plassman, P. 1989. The Steiner problem with edge lengths 1 and 2. Inf. Proc. Lett. 32, 4, 171--176. Google ScholarDigital Library
- Charikar, M., and Karagiozova, A. 2005. On non-uniform multicommodity buy-at-bulk network design. In Proceedings of the 37th Annual ACM Symposium on the Theory of Computing (STOC). ACM, New York, 176--182. Google ScholarDigital Library
- Chekuri, C., Hajiaghayi, M. T., Kortsarz, G., and Salavatipour, M. R. 2006. Approximation algorithms for non-uniform buy-at-bulk network design problems. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 677--686. Google ScholarDigital Library
- Chekuri, C., Khanna, S., and Naor, J. 2001. A deterministic algorithm for the Cost-Distance problem. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 232--233. Google ScholarDigital Library
- Chuzhoy, J., Gupta, A., Naor, J., and Sinha, A. 2005. On the approximability of some network design problems. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 943--951. Google ScholarDigital Library
- Cole, R., Hariharan, R., Lewenstein, M., and Porat, E. 2001. A faster implementation of the Goemans-Williamson clustering algorithm. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 17--25. Google ScholarDigital Library
- Duffield, N. G., Goyal, P., Greenberg, A. G., Mishra, P. P., Ramakrishnan, K. K., and van der Merwe, J. E. 1999. A flexible model for resource management in virtual private networks. In Proceedings of SIGCOMM. ACM, New York, 95--108. Google ScholarDigital Library
- Eisenbrand, F., and Grandoni, F. 2005. An improved approximation algorithm for virtual private network design. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 928--932. Google ScholarDigital Library
- Eisenbrand, F., Grandoni, F., and Rothvoß, T. 2007. A tighter analysis of random sampling for connected facility location. Submitted.Google Scholar
- 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. Google ScholarDigital Library
- Fakcharoenphol, J., Rao, S., and Talwar, K. 2004. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69, 3, 485--497. Google ScholarDigital Library
- Fingerhut, J. A., Suri, S., and Turner, J. S. 1997. Designing least-cost nonblocking broadband networks. J. Algorithms 24, 2, 287--309. Google ScholarDigital Library
- Fleischer, L. K., Könemann, J., Leonardi, S., and Schäfer, G. 2006. Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree. In Proceedings of the 38th Annual ACM Symposium on the Theory of Computing (STOC). ACM, New York, 663--670. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- Goemans, M. X., and Williamson, D. P. 1995. A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 2, 296--317. (Preliminary version in 5th SODA, 1994). Google ScholarDigital Library
- Goemans, M. X., and Williamson, D. P. 1997. The primal-dual method for approximation algorithms and its application to network design problems. In Approximation Algorithms for NP-hard Problems, D. S. Hochbaum, Ed. PWS Publishing. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Guha, S., Meyerson, A., and Munagala, K. 2000. Hierarchical placement and network design problems. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 603--612. Google ScholarDigital Library
- Guha, S., Meyerson, A., and Munagala, K. 2001. A constant factor approximation for the single sink edge installation problems. In Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing (STOC). ACM, New York, 383--388. Google ScholarDigital Library
- Gupta, A., Hajiaghayi, M. T., and Räcke, H. 2006. Oblivious network design. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 970--979. Google ScholarDigital Library
- Gupta, A., Kumar, A., Kleinberg, J., Rastogi, R., and Yener, B. 2001. Provisioning a Virtual Private Network: A network design problem for multicommodity flow. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC). ACM, New York, 389--398. Google ScholarDigital Library
- Gupta, A., Kumar, A., Pál, M., and Roughgarden, T. 2003a. 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 (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 606--615. Google ScholarDigital Library
- Gupta, A., Kumar, A., and Roughgarden, T. 2003b. Simpler and better approximation algorithms for network design. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC). ACM, New York, 365--372. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Gupta, A., Pál, M., Ravi, R., and Sinha, A. 2004a. Boosted sampling: Approximation algorithms for stochastic optimization. In Proceedings of the 36th Annual ACM Symposium on the Theory of Computing (STOC). ACM, New York, 417--426. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- Hassin, R., Ravi, R., and Salman, F. S. 2004. Approximation algorithms for a capacitated network design problem. Algorithmica 38, 3, 417--431.Google ScholarDigital Library
- Hayrapetyan, A., Swamy, C., and Tardos, É. 2005. Network design for information networks. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 933--942. Google ScholarDigital Library
- Immorlica, N., Karger, D. R., Minkoff, M., and Mirrokni, V. S. 2004. On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 691--700. Google ScholarDigital Library
- Jain, K., and Vazirani, V. 2001. Applications of approximation algorithms to cooperative games. In Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing (STOC). ACM, New York, 364--372. Google ScholarDigital Library
- Jain, K., and Vazirani, V. 2002. Equitable cost allocations via primal-dual-type algorithms. In Proceedings of the 34th Annual ACM Symposium on the Theory of Computing (STOC). ACM, New York, 313--321. Google ScholarDigital Library
- Karger, D. R., and Minkoff, M. 2000. Building Steiner trees with incomplete global knowledge. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 613--623. Google ScholarDigital Library
- Khuller, S., and Zhu, A. 2002. The General Steiner tree-star problem. Inf. Proc. Lett. 84, 4, 215--220. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Klein, P. N. 1994. A data structure for bicategories, with application to speeding up an approximation algorithm. Inf. Proc. Lett. 52, 6, 303--307. Google ScholarDigital Library
- Könemann, J., Leonardi, S., and Schäfer, G. 2005. A group-strategyproof mechanism for Steiner forests. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 612--619. Google ScholarDigital Library
- Kumar, A., Gupta, A., and Roughgarden, T. 2002. 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 (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 333--342. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarDigital Library
- Meyerson, A., Munagala, K., and Plotkin, S. 2000. Cost-distance: Two metric network design. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 624--630. Google ScholarDigital Library
- Meyerson, A., Munagala, K., and Plotkin, S. 2001. Designing networks incrementally. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 406--415. Google ScholarDigital Library
- Pál, M. 2004. Cost sharing and approximation. Ph.D. dissertation, Cornell University.Google Scholar
- Pál, M., and Tardos, É. 2003. Group strategyproof mechanisms via primal-dual algorithms. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 584--593. Google ScholarDigital Library
- Ravi, R., and Salman, F. S. 1999. Approximation algorithms for the traveling purchaser problem and its variants in network design. In Proceedings of the 7th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 1643. Springer-Verlag, New York, 29--40. Google ScholarDigital Library
- Ravi, R., and Sinha, A. 2006. Hedging uncertainty: Approximation algorithms for stochastic optimiza tion problems. Math. Prog. 108, 1, 97--114. Google ScholarDigital Library
- Robins, G., and Zelikovsky, A. 2005. Tighter bounds for graph Steiner tree approximation. SIAM J. Disc. Math. 19, 1, 122--134. Google ScholarDigital Library
- Salman, F. S., Cheriyan, J., Ravi, R., and Subramanian, S. 2000. Approximating the single-sink link-installation problem in network design. SIAM J. Optim. 11, 3, 595--610 (Preliminary version in 8th SODA, 1997). Google ScholarDigital Library
- Swamy, C., and Kumar, A. 2004. Primal-dual algorithms for connected facility location problems. Algorithmica 40, 4, 245--269. Google ScholarDigital Library
- Talwar, K. 2002. Single-sink buy-at-bulk LP has constant integrality gap. In Proceedings of the 9th Integer Programming and Combinatorial Optimization Conference (IPCO). Lecture Notes in Computer Science, vol. 2337. Springer-Verlag, New York, 475--486. Google ScholarDigital Library
- Vazirani, V. V. 2001. Approximation Algorithms. Springer-Verlag, Berlin, Germany. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
Index Terms
- Approximation via cost sharing: Simpler and better approximation algorithms for network design
Recommendations
Simpler and better approximation algorithms for network design
STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computingWe give simple and easy-to-analyze randomized approximation algorithms for several well-studied NP-hard network design problems. Our algorithms improve over the previously best known approximation ratios. Our main results are the following.
- We give a ...
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 ...
Cost sharing on prices for games on graphs
Let $$N=\{1,\dots ,n\}$$N={1,ź,n} be a set of customers who want to buy a single homogenous goods in market. Let $$q_i>0$$qi>0 be the quantity that $$i\in N$$iźN demands, $$q=(q_1,\dots ,q_n)$$q=(q1,ź,qn) and $$q_S=\sum _{i\in S}q_i$$qS=źiźSqi for $$S\...
Comments