{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:14:09Z","timestamp":1759335249191,"version":"3.41.0"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,5,30]],"date-time":"2018-05-30T00:00:00Z","timestamp":1527638400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"crossref"}]},{"name":"FONDECYT"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,3]]},"DOI":"10.1007\/s00453-018-0458-x","type":"journal-article","created":{"date-parts":[[2018,5,30]],"date-time":"2018-05-30T17:20:55Z","timestamp":1527700855000},"page":"1075-1095","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["LP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design"],"prefix":"10.1007","volume":"81","author":[{"given":"Zachary","family":"Friggstad","sequence":"first","affiliation":[]},{"given":"Mohsen","family":"Rezapour","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7650-2045","authenticated-orcid":false,"given":"Mohammad R.","family":"Salavatipour","sequence":"additional","affiliation":[]},{"given":"Jose A.","family":"Soto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,5,30]]},"reference":[{"key":"458_CR1","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.dam.2016.05.016","volume":"213","author":"A Bley","year":"2016","unstructured":"Bley, A., Rezapour, M.: Combinatorial approximation algorithms for buy-at-bulk connected facility location problems. Discrete Appl. Math. 213, 34\u201346 (2016)","journal-title":"Discrete Appl. Math."},{"unstructured":"Chekuri, C., Khanna, S., Naor, J.S.: A deterministic algorithm for the cost-distance problem. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 232\u2013233 (2001)","key":"458_CR2"},{"issue":"8","key":"458_CR3","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1016\/j.jcss.2010.02.001","volume":"76","author":"F Eisenbrand","year":"2010","unstructured":"Eisenbrand, F., Grandoni, F., Rothvo\u00df, T., Sch\u00e4fer, G.: Connected facility location via random facility sampling and core detouring. J. Comput. Syst. Sci. 76(8), 709\u2013726 (2010)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Friggstad, Z., Rezapour, M., Salavatipour, M.R., Soto, J.A.: LP-based approximation algorithms for facility location in buy-at-bulk network design. In: Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS), pp. 373\u2013385 (2015)","key":"458_CR4","DOI":"10.1007\/978-3-319-21840-3_31"},{"doi-asserted-by":"crossref","unstructured":"Garg, N., Khandekar, R., Konjevod, G., Ravi, R., Salman, F.S., Sinha, A.: On the integrality gap of a natural formulation of the single-sink buy-at-bulk network design problem. In: Proceedings of Integer Programming and Combinatorial Optimization (IPCO), pp. 170\u2013184 (2001)","key":"458_CR5","DOI":"10.1007\/3-540-45535-3_14"},{"doi-asserted-by":"crossref","unstructured":"Grandoni, F., Rothvo\u00df, T.: Network design via core detouring for problems without a core. In: Proceedings of International Colloquium on Automata, Languages, and Programming (ICALP), pp. 490\u2013502 (2010)","key":"458_CR6","DOI":"10.1007\/978-3-642-14165-2_42"},{"doi-asserted-by":"crossref","unstructured":"Grandoni, F., Rothvo\u00df, T.: Approximation algorithms for single and multi-commodity connected facility location. In: Proceedings of Integer Programming and Combinatorial Optimization (IPCO), pp. 248\u2013260 (2011)","key":"458_CR7","DOI":"10.1007\/978-3-642-20807-2_20"},{"issue":"2","key":"458_CR8","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1287\/moor.1110.0490","volume":"36","author":"F Grandoni","year":"2011","unstructured":"Grandoni, F., Rothvo\u00df, T., Sanit\u00e0, L.: From uncertainty to nonlinearity: solving virtual private network via single-sink buy-at-bulk. Math. Oper. Res. 36(2), 185\u2013204 (2011)","journal-title":"Math. Oper. Res."},{"issue":"6","key":"458_CR9","doi-asserted-by":"publisher","first-page":"2426","DOI":"10.1137\/050643635","volume":"38","author":"S Guha","year":"2009","unstructured":"Guha, S., Meyerson, A., Munagala, K.: A constant factor approximation for the single sink edge installation problem. SIAM J. Comput. 38(6), 2426\u20132442 (2009)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Gupta, A., Kleinberg, J., Kumar, A., Rastogi, R., Yener, B.: Provisioning a virtual private network: a network design problem for multicommodity flow. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (STOC), pp. 389\u2013398 (2001)","key":"458_CR10","DOI":"10.1145\/380752.380830"},{"doi-asserted-by":"crossref","unstructured":"Jothi, R., Raghavachari, B.: Improved approximation algorithms for the single-sink buy-at-bulk network design problems. In: Proceedings of Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 336\u2013348 (2004)","key":"458_CR11","DOI":"10.1007\/978-3-540-27810-8_29"},{"issue":"4","key":"458_CR12","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/BF01294129","volume":"14","author":"S Khuller","year":"1995","unstructured":"Khuller, S., Raghavachari, B., Young, N.: Balancing minimum spanning trees and shortest-path trees. Algorithmica 14(4), 305\u2013321 (1995)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Meyerson, A., Munagala, K., Plotkin, S.: Cost-distance: two metric network design. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), pp. 624\u2013630 (2000)","key":"458_CR13","DOI":"10.1109\/SFCS.2000.892330"},{"issue":"1","key":"458_CR14","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1287\/opre.1050.0228","volume":"54","author":"R Ravi","year":"2006","unstructured":"Ravi, R., Sinha, A.: Approximation algorithms for problems combining facility location and network design. Oper. Res. 54(1), 73\u201381 (2006)","journal-title":"Oper. Res."},{"doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tardos, \u00c9., Aardal, K.: Approximation algorithms for facility location problems. In: Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), pp. 265\u2013274 (1997)","key":"458_CR15","DOI":"10.1145\/258533.258600"},{"issue":"4","key":"458_CR16","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00453-004-1112-3","volume":"40","author":"C Swamy","year":"2004","unstructured":"Swamy, C., Kumar, A.: Primal-dual algorithms for connected facility location problems. Algorithmica 40(4), 245\u2013269 (2004)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Talwar, K.: The single-sink buy-at-bulk lp has constant integrality gap. In: Proceedings of Integer Programming and Combinatorial Optimization (IPCO), pp. 475\u2013486 (2002)","key":"458_CR17","DOI":"10.1007\/3-540-47867-1_33"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0458-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0458-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0458-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T21:58:35Z","timestamp":1751666315000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0458-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,30]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,3]]}},"alternative-id":["458"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0458-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,5,30]]},"assertion":[{"value":"17 December 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 May 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}