{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:57:34Z","timestamp":1781305054006,"version":"3.54.1"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032286901","type":"print"},{"value":"9783032286918","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-28691-8_8","type":"book-chapter","created":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:35:10Z","timestamp":1781303710000},"page":"112-127","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximating Multiple-Depot Capacitated Vehicle Routing via\u00a0LP Rounding"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4039-3235","authenticated-orcid":false,"given":"Zachary","family":"Friggstad","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2509-6972","authenticated-orcid":false,"given":"Tobias","family":"M\u00f6mke","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,13]]},"reference":[{"key":"8_CR1","unstructured":"Armbruster, S., Mnich, M., N\u00e4gele, M.: A (3\/2 + 1\/e)-approximation algorithm for ordered TSP. In: Kumar, A., Ron-Zewi, N. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2024, London School of Economics, London, UK, 28\u201330 August 2024. LIPIcs, vol.\u00a0317, pp. 1:1\u20131:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024)"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Asano, T., Katoh, N., Tamaki, H., Tokuyama, T.: Covering points in the plane by $$k$$-tours: towards a polynomial time approximation scheme for general $$k$$. In: ACM Symposium on Theory of Computing (STOC), pp. 275\u2013283 (1997)","DOI":"10.1145\/258533.258602"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Bang-Jensen, J., Frank, A., Jackson, B.: Preserving and increasing local edge-connectivity in mixed graphs. SIAM J. Disc. Math. 8, 155\u2013178 (1995). https:\/\/api.semanticscholar.org\/CorpusID:17614575","DOI":"10.1137\/S0036142993226983"},{"issue":"2","key":"8_CR4","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s10107-022-01841-4","volume":"197","author":"J Blauth","year":"2023","unstructured":"Blauth, J., Traub, V., Vygen, J.: Improving the approximation ratio for capacitated vehicle routing. Math. Program. 197(2), 451\u2013497 (2023)","journal-title":"Math. Program."},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"B\u00f6hm, M., Friggstad, Z., M\u00f6mke, T., Spoerhase, J.: Approximating traveling salesman problems using a bridge lemma. In: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM (2025)","DOI":"10.1137\/1.9781611978322.34"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e0, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 6:1\u20136:33 (2013)","DOI":"10.1145\/2432622.2432628"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Byrka, J., Grandoni, F., Rothvoss, T., Sanit\u00e0, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1) (2013)","DOI":"10.1145\/2432622.2432628"},{"issue":"4","key":"8_CR8","doi-asserted-by":"publisher","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71","author":"J Edmonds","year":"1967","unstructured":"Edmonds, J.: Optimum branchings. J. Res. Natl. Bureau Stand. B 71(4), 233\u2013240 (1967)","journal-title":"J. Res. Natl. Bureau Stand. B"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Haimovich, M., Rinnooy\u00a0Kan, A.H.G.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527\u2013542 (1985)","DOI":"10.1287\/moor.10.4.527"},{"issue":"1","key":"8_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1287\/trsc.1120.0423","volume":"47","author":"T Harks","year":"2013","unstructured":"Harks, T., K\u00f6nig, F.G., Matuschke, J.: Approximation algorithms for capacitated location routing. Transp. Sci. 47(1), 3\u201322 (2013)","journal-title":"Transp. Sci."},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Karlin, A.R., Klein, N., Oveis Gharan, S.: A (slightly) improved approximation algorithm for metric tsp. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 32\u201345 (2021)","DOI":"10.1145\/3406325.3451009"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Karlin, A.R., Klein, N., Oveis Gharan, S.: A deterministic better-than-3\/2 approximation algorithm for metric TSP. In: Pia, A.D., Kaibel, V. (eds.) Proceedings of 24th International Integer Programming and Combinatorial Optimization (IPCO\u201923), pp. 261\u2013274 (2023)","DOI":"10.1007\/978-3-031-32726-1_19"},{"issue":"1","key":"8_CR13","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1287\/ijoc.2.1.64","volume":"2","author":"CL Li","year":"1990","unstructured":"Li, C.L., Simchi-Levi, D.: Worst-case analysis of heuristics for multidepot capacitated vehicle routing problems. ORSA J. Comput. 2(1), 64\u201373 (1990)","journal-title":"ORSA J. Comput."},{"key":"8_CR14","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.cie.2014.10.029","volume":"79","author":"JR Montoya-Torres","year":"2015","unstructured":"Montoya-Torres, J.R., Franco, J.L., Isaza, S.N., Jim\u00e9nez, H.F., Herazo-Padilla, N.: A literature review on the vehicle routing problem with multiple depots. Comput. Ind. Eng. 79, 115\u2013129 (2015)","journal-title":"Comput. Ind. Eng."},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Post, I., Swamy, C.: Linear programming-based approximation algorithms for multi-vehicle minimum latency problems. In: Proceedings of 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915), pp. 512\u2013531 (2015)","DOI":"10.1137\/1.9781611973730.35"},{"key":"8_CR16","doi-asserted-by":"publisher","unstructured":"Zhao, J., Xiao, M.: Improved approximation algorithms for multidepot capacitated vehicle routing. In: COCOON (2). Lecture Notes in Computer Science, vol. 14423, pp. 378\u2013391. Springer, Heidelberg (2023). https:\/\/doi.org\/10.1007\/978-3-031-49193-1_29","DOI":"10.1007\/978-3-031-49193-1_29"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-28691-8_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:35:13Z","timestamp":1781303713000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-28691-8_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032286901","9783032286918"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-28691-8_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Padua","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.math.unipd.it\/ipco2026\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}