{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:46:56Z","timestamp":1781077616105,"version":"3.54.1"},"reference-count":31,"publisher":"IEEE Computer. Soc","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/sfcs.2003.1238233","type":"proceedings-article","created":{"date-parts":[[2004,3,2]],"date-time":"2004-03-02T02:26:50Z","timestamp":1078194410000},"page":"606-615","source":"Crossref","is-referenced-by-count":28,"title":["Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem"],"prefix":"10.1109","author":[{"given":"A.","family":"Gupta","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"A.","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M.","family":"Pal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"T.","family":"Roughgarden","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"263","reference":[{"key":"19","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1145\/780542.780597","article-title":"Simpler and better approximation algorithms for network design","author":"gupta","year":"2003","journal-title":"30th STOC"},{"key":"17","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380827"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380830"},{"key":"15","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892328"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45535-3_14"},{"key":"14","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1155-0"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780608"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548489"},{"key":"21","first-page":"613","article-title":"Building Steiner trees with incomplete global knowledge","author":"karger","year":"2000","journal-title":"FOCS 43"},{"key":"20","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380825"},{"key":"22","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00271-5"},{"key":"23","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199610)28:3<167::AID-NET5>3.0.CO;2-L"},{"key":"24","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1181956"},{"key":"25","first-page":"624","article-title":"Cost-distance: Two metric network design","author":"meyerson","year":"2000","journal-title":"FOCS 43"},{"key":"26","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959915"},{"key":"27","first-page":"29","article-title":"Approximation algorithms for the traveling purchaser problem and its variants in network design","author":"ravi","year":"1999","journal-title":"ESA '99 Volume 1643 of LNCS"},{"key":"28","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497321432"},{"key":"29","first-page":"256","article-title":"Primal-dual algorithms for the connected facility location problem","author":"swamy","year":"2002","journal-title":"5th APPROX Volume 2462 of LNCS"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646143"},{"key":"2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-0968-3"},{"key":"10","first-page":"232","article-title":"A deterministic algorithm for the cost-distance problem","author":"chekuri","year":"2001","journal-title":"13th SODA"},{"key":"1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"30","first-page":"475","article-title":"Single-sink buy-at-bulk LP has constant integrality gap","author":"talwar","year":"2002","journal-title":"9th IPCO Volume 2337 of LNCS"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1073"},{"key":"6","first-page":"43","article-title":"On-line generalized steiner problem","author":"bartal","year":"1997","journal-title":"7th SODA"},{"key":"5","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276725"},{"key":"31","first-page":"1193","article-title":"Cost allocation","volume":"2","author":"young","year":"1994","journal-title":"Handbook of Game Theory"},{"key":"4","first-page":"68","article-title":"On-line generalized Steiner problem","author":"awerbuch","year":"1996","journal-title":"7th SODA"},{"key":"9","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90039-2"}],"event":{"name":"44th Annual IEEE Symposium on Foundations of Computer Science - FOCS 2003","location":"Cambridge, MA, USA","acronym":"SFCS-03"},"container-title":["44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings."],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/8767\/27770\/01238233.pdf?arnumber=1238233","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,28]],"date-time":"2023-04-28T01:42:05Z","timestamp":1682646125000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/1238233\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":31,"URL":"https:\/\/doi.org\/10.1109\/sfcs.2003.1238233","relation":{},"subject":[]}}