{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:14:34Z","timestamp":1773656074610,"version":"3.50.1"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2007,6,1]],"date-time":"2007-06-01T00:00:00Z","timestamp":1180656000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2007,6]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/1236457.1236458","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"11","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":51,"title":["Approximation via cost sharing"],"prefix":"10.1145","volume":"54","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, Pennsylvania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amit","family":"Kumar","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, New Delhi, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"P\u00b4al","sequence":"additional","affiliation":[{"name":"Google, Inc., New York, New York"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tim","family":"Roughgarden","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, California"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.32"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-0968-3"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Awerbuch B."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.021"},{"key":"e_1_2_1_7_1","unstructured":"Bartal Y. 1994. Competitive analysis of distributed on-line problems---Distributed paging. Ph.D. dissertation Tel-Aviv University Tel-Aviv Israel.  Bartal Y. 1994. Competitive analysis of distributed on-line problems---Distributed paging. Ph.D. dissertation Tel-Aviv University Tel-Aviv Israel."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875536"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276725"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00259-0"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1073"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Becchetti L."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90039-2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060617"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.15"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Chekuri C."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Chuzhoy J."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Cole R."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316209"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Eisenbrand F."},{"key":"e_1_2_1_21_1","unstructured":"Eisenbrand F. Grandoni F. and Rothvo\u00df T. 2007. A tighter analysis of random sampling for connected facility location. Submitted.  Eisenbrand F. Grandoni F. and Rothvo\u00df T. 2007. A tighter analysis of random sampling for connected facility location. Submitted."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_93"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0866"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132609"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585864"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1155-0"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_2_1_29_1","unstructured":"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.   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."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/11940128_13"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Guha S."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380827"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109665"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380830"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Gupta A."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780597"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_85"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007419"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_8"},{"key":"e_1_2_1_40_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)","author":"Gupta A."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1069-7"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Hayrapetyan A.","year":"2005"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Immorlica N."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380825"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509956"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Karger D. R."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00271-5"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199610)28:3<167::AID-NET5>3.0.CO;2-L"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00156-1"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"K\u00f6nemann J."},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Kumar A."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.8.3.194"},{"key":"e_1_2_1_54_1","volume-title":"Cost-distance: Two metric network design. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Meyerson A.","year":"2000"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Meyerson A."},{"key":"e_1_2_1_56_1","unstructured":"P\u00e1l M. 2004. Cost sharing and approximation. Ph.D. dissertation Cornell University.  P\u00e1l M. 2004. Cost sharing and approximation. Ph.D. dissertation Cornell University."},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"P\u00e1l M.","year":"2003"},{"key":"e_1_2_1_58_1","volume-title":"Proceedings of the 7th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science","volume":"1643","author":"Ravi R."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0673-5"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101393155"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497321432"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1112-3"},{"key":"e_1_2_1_63_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 9th Integer Programming and Combinatorial Optimization Conference (IPCO)","author":"Talwar K."},{"key":"e_1_2_1_64_1","unstructured":"Vazirani V. V. 2001. Approximation Algorithms. Springer-Verlag Berlin Germany.   Vazirani V. V. 2001. Approximation Algorithms. Springer-Verlag Berlin Germany."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2007.02.005"},{"key":"e_1_2_1_66_1","first-page":"1193","article-title":"Cost allocation. In Handbook of Game Theory, R. J. Aumann and S. Hart, Eds. Vol. 2. North-Holland, Amsterdam, The Netherlands","volume":"34","author":"Young H. P.","year":"1994","journal-title":"Chap."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1236457.1236458","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1236457.1236458","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:07Z","timestamp":1750258327000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1236457.1236458"}},"subtitle":["Simpler and better approximation algorithms for network design"],"short-title":[],"issued":{"date-parts":[[2007,6]]},"references-count":65,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,6]]}},"alternative-id":["10.1145\/1236457.1236458"],"URL":"https:\/\/doi.org\/10.1145\/1236457.1236458","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,6]]},"assertion":[{"value":"2007-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}