{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T19:10:02Z","timestamp":1748545802533,"version":"3.41.0"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319218397"},{"type":"electronic","value":"9783319218403"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21840-3_31","type":"book-chapter","created":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T09:57:38Z","timestamp":1437991058000},"page":"373-385","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["LP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design"],"prefix":"10.1007","author":[{"given":"Zachary","family":"Friggstad","sequence":"first","affiliation":[]},{"given":"Mohsen","family":"Rezapour","sequence":"additional","affiliation":[]},{"given":"Mohammad R.","family":"Salavatipour","sequence":"additional","affiliation":[]},{"given":"Jos\u00e9 A.","family":"Soto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,7,28]]},"reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"Bley, A., Rezapour, M.: Approximating connected facility location with buy-at-bulk edge costs via random sampling. In: Proc. of LAGOS 2013, pp. 313\u2013319 (2013)","DOI":"10.1016\/j.endm.2013.10.049"},{"key":"31_CR2","unstructured":"Chekuri, C., Khanna, S., Naor, J.S.: A deterministic algorithm for the cost-distance problem. In: Proc. of SODA 2001, pp. 232\u2013233 (2001)"},{"issue":"8","key":"31_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. Journal of Computer and System Sciences 76(8), 709\u2013726 (2010)","journal-title":"Journal of Computer and System Sciences"},{"key":"31_CR4","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 formulation. In: Proc. of IPCO 2001, pp. 170\u2013184 (2001)","DOI":"10.1007\/3-540-45535-3_14"},{"key":"31_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/978-3-642-14165-2_42","volume-title":"Automata, Languages and Programming","author":"F Grandoni","year":"2010","unstructured":"Grandoni, F., Rothvo\u00df, T.: Network design via core detouring for problems without a core. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 490\u2013502. Springer, Heidelberg (2010)"},{"key":"31_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/978-3-642-20807-2_20","volume-title":"Integer Programming and Combinatoral Optimization","author":"F Grandoni","year":"2011","unstructured":"Grandoni, F., Rothvo\u00df, T.: Approximation algorithms for single and multi-commodity connected facility location. In: G\u00fcnl\u00fck, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 248\u2013260. Springer, Heidelberg (2011)"},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"Guha, S., Meyerson, A., Munagala, K.: A constant factor approximation for the single sink edge installation problems. In: Proc. of STOC 2001, pp. 383\u2013388 (2001)","DOI":"10.1145\/380752.380827"},{"key":"31_CR8","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: Proc. of STOC 2001, pp. 389\u2013398 (2001)","DOI":"10.1145\/380752.380830"},{"key":"31_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/978-3-540-27810-8_29","volume-title":"Algorithm Theory - SWAT 2004","author":"R Jothi","year":"2004","unstructured":"Jothi, R., Raghavachari, B.: Improved approximation algorithms for the single-sink buy-at-bulk network design problems. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 336\u2013348. Springer, Heidelberg (2004)"},{"issue":"4","key":"31_CR10","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/BF01294129","volume":"14","author":"S Khuller","year":"1994","unstructured":"Khuller, S., Raghavachari, B., Young, N.: Balancing minimum spanning and shortest path trees. Algorithmica 14(4), 305\u2013321 (1994)","journal-title":"Algorithmica"},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"Meyerson, A., Munagala, K., Plotkin, S.: Cost-distance: two metric network design. In: Proc. of FOCS 2000, pp. 624\u2013630 (2000)","DOI":"10.1109\/SFCS.2000.892330"},{"key":"31_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/3-540-47867-1_16","volume-title":"Integer Programming and Combinatorial Optimization","author":"R Ravi","year":"2002","unstructured":"Ravi, R., Sinha, A.: Integrated logistics: approximation algorithms combining facility location and network design. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol. 2337, pp. 212\u2013229. Springer, Heidelberg (2002)"},{"key":"31_CR13","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tardos, E., Aardal, K.I.: Approximation algorithms for facility location problems. In: Proc. of STOC 1997, pp. 265\u2013274 (1997)","DOI":"10.1145\/258533.258600"},{"issue":"4","key":"31_CR14","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"},{"key":"31_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/3-540-47867-1_33","volume-title":"Integer Programming and Combinatorial Optimization","author":"K Talwar","year":"2002","unstructured":"Talwar, K.: The single-sink buy-at-bulk LP has constant integrality gap. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol. 2337, pp. 475\u2013480. Springer, Heidelberg (2002)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21840-3_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T18:50:07Z","timestamp":1748544607000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21840-3_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319218397","9783319218403"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21840-3_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"28 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}