{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:14:39Z","timestamp":1781345679305,"version":"3.54.1"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031491924","type":"print"},{"value":"9783031491931","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-49193-1_29","type":"book-chapter","created":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T09:02:36Z","timestamp":1702026156000},"page":"378-391","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Improved Approximation Algorithms for\u00a0Multidepot Capacitated Vehicle Routing"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2322-750X","authenticated-orcid":false,"given":"Jingyang","family":"Zhao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1012-2373","authenticated-orcid":false,"given":"Mingyu","family":"Xiao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,12,9]]},"reference":[{"issue":"4","key":"29_CR1","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0167-6377(87)90012-5","volume":"6","author":"K Altinkemer","year":"1987","unstructured":"Altinkemer, K., Gavish, B.: Heuristics for unequal weight delivery problems with a fixed error guarantee. Oper. Res. Lett. 6(4), 149\u2013158 (1987)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"29_CR2","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1287\/trsc.24.4.294","volume":"24","author":"K Altinkemer","year":"1990","unstructured":"Altinkemer, K., Gavish, B.: Heuristics for delivery problems with constant error guarantees. Transp. Sci. 24(4), 294\u2013297 (1990)","journal-title":"Transp. Sci."},{"key":"29_CR3","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: STOC 1997, pp. 275\u2013283. ACM (1997)","DOI":"10.1145\/258533.258602"},{"key":"29_CR4","doi-asserted-by":"crossref","unstructured":"Blauth, J., Traub, V., Vygen, J.: Improving the approximation ratio for capacitated vehicle routing. Math. Program., 1\u201347 (2022)","DOI":"10.1007\/978-3-030-73879-2_1"},{"issue":"4","key":"29_CR5","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.disopt.2006.04.002","volume":"3","author":"A Bompadre","year":"2006","unstructured":"Bompadre, A., Dror, M., Orlin, J.B.: Improved bounds for vehicle routing solutions. Discret. Optim. 3(4), 299\u2013316 (2006)","journal-title":"Discret. Optim."},{"key":"29_CR6","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Carnegie-Mellon University, Tech. rep. (1976)"},{"issue":"3","key":"29_CR7","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chvatal","year":"1979","unstructured":"Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"key":"29_CR8","unstructured":"Deppert, M., Kaul, M., Mnich, M.: A (3\/2+ $$\\varepsilon $$)-approximation for multiple tsp with a variable number of depots. In: 31st Annual European Symposium on Algorithms (ESA 2023). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2023)"},{"key":"29_CR9","doi-asserted-by":"publisher","unstructured":"Friggstad, Z., Mousavi, R., Rahgoshay, M., Salavatipour, M.R.: Improved approximations for capacitated vehicle routing with unsplittable client demands. In: IPCO 2022. LNCS, vol. 13265, pp. 251\u2013261. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-06901-7_19","DOI":"10.1007\/978-3-031-06901-7_19"},{"key":"29_CR10","doi-asserted-by":"crossref","unstructured":"Gupta, A., Lee, E., Li, J.: A local search-based approach for set covering. In: SOSA 2023, pp. 1\u201311. SIAM (2023)","DOI":"10.1137\/1.9781611977585.ch1"},{"issue":"4","key":"29_CR11","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1287\/moor.10.4.527","volume":"10","author":"M Haimovich","year":"1985","unstructured":"Haimovich, M., Kan, A.H.G.R.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527\u2013542 (1985)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"29_CR12","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."},{"issue":"1","key":"29_CR13","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1137\/S0097539704444750","volume":"35","author":"R Hassin","year":"2005","unstructured":"Hassin, R., Levin, A.: A better-than-greedy approximation algorithm for the minimum set cover problem. SIAM J. Comput. 35(1), 189\u2013200 (2005)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"29_CR14","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1016\/j.ejor.2022.04.028","volume":"304","author":"FC Heine","year":"2023","unstructured":"Heine, F.C., Demleitner, A., Matuschke, J.: Bifactor approximation for location routing with vehicle and facility capacities. Eur. J. Oper. Res. 304(2), 429\u2013442 (2023)","journal-title":"Eur. J. Oper. Res."},{"key":"29_CR15","doi-asserted-by":"crossref","unstructured":"Karlin, A.R., Klein, N., Gharan, S.O.: A (slightly) improved approximation algorithm for metric TSP. In: STOC 2021, pp. 32\u201345. ACM (2021)","DOI":"10.1145\/3406325.3451009"},{"key":"29_CR16","doi-asserted-by":"publisher","unstructured":"Karlin, A.R., Klein, N., Gharan, S.O.: A deterministic better-than-3\/2 approximation algorithm for metric TSP. In: IPCO 2023. LNCS, vol. 13904, pp. 261\u2013274. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-32726-1_19","DOI":"10.1007\/978-3-031-32726-1_19"},{"key":"29_CR17","doi-asserted-by":"crossref","unstructured":"Lai, X., Xu, L., Xu, Z., Du, Y.: An approximation algorithm for k-depot split delivery vehicle routing problem. INFORMS J. Comput. (2023)","DOI":"10.1287\/ijoc.2021.0193.cd"},{"issue":"1","key":"29_CR18","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1287\/ijoc.2.1.64","volume":"2","author":"C Li","year":"1990","unstructured":"Li, C., Simchi-Levi, D.: Worst-case analysis of heuristics for multidepot capacitated vehicle routing problems. INFORMS J. Comput. 2(1), 64\u201373 (1990)","journal-title":"INFORMS J. Comput."},{"key":"29_CR19","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. Indust. Eng. 79, 115\u2013129 (2015)","journal-title":"Comput. Indust. Eng."},{"issue":"1","key":"29_CR20","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1109\/TASE.2006.872110","volume":"4","author":"S Rathinam","year":"2007","unstructured":"Rathinam, S., Sengupta, R., Darbha, S.: A resource allocation algorithm for multivehicle systems with nonholonomic constraints. IEEE Trans. Autom. Sci. Eng. 4(1), 98\u2013104 (2007)","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"29_CR21","first-page":"76","volume":"17","author":"AI Serdyukov","year":"1978","unstructured":"Serdyukov, A.I.: Some extremal bypasses in graphs. Upravlyaemye Sistemy 17, 76\u201379 (1978)","journal-title":"Upravlyaemye Sistemy"},{"issue":"3","key":"29_CR22","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1137\/20M135594X","volume":"51","author":"V Traub","year":"2022","unstructured":"Traub, V., Vygen, J., Zenklusen, R.: Reducing path TSP to TSP. SIAM J. Comput. 51(3), 20\u201324 (2022)","journal-title":"SIAM J. Comput."},{"key":"29_CR23","doi-asserted-by":"crossref","unstructured":"Williamson, D.P., Shmoys, D.B.: The design of approximation algorithms. Cambridge University Press (2011)","DOI":"10.1017\/CBO9780511921735"},{"issue":"4","key":"29_CR24","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1287\/ijoc.2015.0650","volume":"27","author":"Z Xu","year":"2015","unstructured":"Xu, Z., Rodrigues, B.: A 3\/2-approximation algorithm for the multiple tsp with a fixed number of depots. INFORMS J. Comput. 27(4), 636\u2013645 (2015)","journal-title":"INFORMS J. Comput."},{"issue":"3","key":"29_CR25","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/j.orl.2011.03.002","volume":"39","author":"Z Xu","year":"2011","unstructured":"Xu, Z., Xu, L., Rodrigues, B.: An analysis of the extended christofides heuristic for the k-depot tsp. Oper. Res. Lett. 39(3), 218\u2013223 (2011)","journal-title":"Oper. Res. Lett."},{"key":"29_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-030-96772-7_9","volume-title":"Parallel and Distributed Computing, Applications and Technologies","author":"W Yu","year":"2022","unstructured":"Yu, W., Liao, Y.: Approximation and polynomial algorithms for multi-depot capacitated arc routing problems. In: Shen, H., et al. (eds.) PDCAT 2021. LNCS, vol. 13148, pp. 93\u2013100. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-030-96772-7_9"},{"key":"29_CR27","unstructured":"Zhao, J., Xiao, M.: Improved approximation algorithms for capacitated vehicle routing with fixed capacity. CoRR abs\/ arXiv: 2210.16534 (2022)"},{"key":"29_CR28","doi-asserted-by":"crossref","unstructured":"Zhao, J., Xiao, M.: Improved approximation algorithms for multidepot capacitated vehicle routing. CoRR abs\/ arXiv: 2308.14131 (2023)","DOI":"10.1007\/978-3-031-49193-1_29"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-49193-1_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,27]],"date-time":"2023-12-27T17:35:27Z","timestamp":1703698527000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-49193-1_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,9]]},"ISBN":["9783031491924","9783031491931"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-49193-1_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,9]]},"assertion":[{"value":"9 December 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hawaii, HI","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 December 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/theory.utdallas.edu\/COCOON2023\/org.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Springer EquinOCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"146","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"60","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}