{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T00:40:36Z","timestamp":1776127236629,"version":"3.50.1"},"reference-count":27,"publisher":"IEEE Comput. Soc","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/sfcs.2002.1181956","type":"proceedings-article","created":{"date-parts":[[2003,6,26]],"date-time":"2003-06-26T15:35:00Z","timestamp":1056641700000},"page":"333-342","source":"Crossref","is-referenced-by-count":25,"title":["A constant-factor approximation algorithm for the multicommodity rent-or-buy problem"],"prefix":"10.1109","author":[{"given":"A.","family":"Kumar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T.","family":"Roughgarden","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"19","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199610)28:3<167::AID-NET5>3.0.CO;2-L"},{"key":"17","first-page":"613","article-title":"Building Steiner trees with incomplete global knowledge","author":"karger","year":"2000","journal-title":"Proceedings of 41st FOCS"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00271-5"},{"key":"15","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510012"},{"key":"16","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1145\/375827.375845","article-title":"Primal-dual approximation algorithms for metric facility location and k-median problems","volume":"48","author":"jain","year":"2001","journal-title":"Journal of the ACM"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380827"},{"key":"14","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380830"},{"key":"11","first-page":"144","article-title":"The primal-dual method for approximation algorithms and its application to network design problems","author":"goemans","year":"1997","journal-title":"Approximation Algorithms for NP-Hard Problems"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892328"},{"key":"21","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.8.3.194"},{"key":"20","article-title":"The median cycle problem","author":"labbe?","year":"2001"},{"key":"22","first-page":"127","article-title":"A greedy facility location algorithm analyzed using dual fitting","author":"madian","year":"2001","journal-title":"Proceedings of 4th APPROX"},{"key":"23","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497321432"},{"key":"24","article-title":"Primal-dual algorithms for the connected facility location problem","author":"swamy","year":"0","journal-title":"APPROX 2002"},{"key":"25","first-page":"475","article-title":"Single-sink buy-at-bulk LP has constant integrality gap","author":"talwar","year":"2002","journal-title":"Proceedings of 9th IPCO"},{"key":"26","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100262"},{"key":"27","doi-asserted-by":"publisher","DOI":"10.1007\/BF01299747"},{"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","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"7","first-page":"170","article-title":"On the integrality gap of a natural formulation of the single-sink buy-at-bulk network design formulation","author":"garg","year":"2001","journal-title":"Proceedings of 8th IPCO"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00259-0"},{"key":"5","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276725"},{"key":"4","first-page":"68","article-title":"On-line generalized Steiner problem","author":"awerbuch","year":"1996","journal-title":"Proceedings of 7th SODA"},{"key":"9","first-page":"223","article-title":"Improved approximation algorithms for network design problems","author":"goemans","year":"1994","journal-title":"Proceedings of 5th SODA"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580607"}],"event":{"name":"43rd Annual IEEE Symposium on Foundations of Computer Science","location":"Vancouver, BC, Canada","acronym":"SFCS-02"},"container-title":["The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings."],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/8411\/26517\/01181956.pdf?arnumber=1181956","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T22:46:25Z","timestamp":1497566785000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/1181956\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":27,"URL":"https:\/\/doi.org\/10.1109\/sfcs.2002.1181956","relation":{},"subject":[]}}