{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T18:36:43Z","timestamp":1770921403006,"version":"3.50.1"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032178008","type":"print"},{"value":"9783032178015","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-17801-5_19","type":"book-chapter","created":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:12Z","timestamp":1770918792000},"page":"260-273","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the\u00a0Complexity of\u00a0Capacitated Vehicle Routing with\u00a0Order Restrictions"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-4478-8115","authenticated-orcid":false,"given":"Steven","family":"Miltenburg","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8509-7002","authenticated-orcid":false,"given":"Tim","family":"Oosterwijk","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0385-0794","authenticated-orcid":false,"given":"Ren\u00e9","family":"Sitters","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,13]]},"reference":[{"issue":"3","key":"19_CR1","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1137\/20M1326167","volume":"51","author":"A Adamaszek","year":"2022","unstructured":"Adamaszek, A., Czumaj, A., Englert, M., R\u00e4cke, H.: Almost tight bounds for reordering buffer management. SIAM J. Comput. 51(3), 701\u2013722 (2022)","journal-title":"SIAM J. Comput."},{"issue":"06","key":"19_CR2","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1142\/S0129054110007623","volume":"21","author":"A Adamaszek","year":"2010","unstructured":"Adamaszek, A., Czumaj, A., Lingas, A.: PTAS for $$k$$-tour cover problem on the plane for moderately large values of $$k$$. Int. J. Found. Comput. Sci. 21(06), 893\u2013904 (2010)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"4","key":"19_CR3","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."},{"issue":"2","key":"19_CR4","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1023\/A:1011461300596","volume":"5","author":"T Asano","year":"2001","unstructured":"Asano, T., Katoh, N., Kawashima, K.: A new approximation algorithm for the capacitated vehicle routing problem on a tree. J. Comb. Optim. 5(2), 213\u2013231 (2001)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"19_CR5","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"19_CR6","unstructured":"Becker, A.: A tight 4\/3 approximation for capacitated vehicle routing in trees. In: Blais, E., Jansen, K., Rolim, J.D.P., Steurer, D. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 116, pp. 3:1\u20133:15. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2018)"},{"issue":"2","key":"19_CR7","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":"19_CR8","doi-asserted-by":"crossref","unstructured":"Das, A., Mathieu, C.: A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp. 390\u2013403. Society for Industrial and Applied Mathematics (2010)","DOI":"10.1137\/1.9781611973075.33"},{"key":"19_CR9","unstructured":"Grandoni, F., Mathieu, C., Zhou, H.: Unsplittable Euclidean capacitated vehicle routing: a $$(2+\\epsilon )$$-approximation algorithm (2022)"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Haimovich, M., Rinnooy Kan, A.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527\u2013542 (1985)","DOI":"10.1287\/moor.10.4.527"},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"Hamaguchi, S., Katoh, N.: A capacitated vehicle routing problem on a tree. In: Chwa, K.-Y., Ibarra, O.H. (eds.) Algorithms and Computation, pp. 399\u2013407. Springer, Heidelberg (1998)","DOI":"10.1007\/3-540-49381-6_42"},{"issue":"1","key":"19_CR12","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"V Kann","year":"1991","unstructured":"Kann, V.: Maximum bounded 3-dimensional matching is MAX SNP-complete. Inf. Process. Lett. 37(1), 27\u201335 (1991)","journal-title":"Inf. Process. Lett."},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Khachay, M., Dubinin, R.: Approximability of the d-dimensional Euclidean capacitated vehicle routing problem. In: AIP Conference Proceedings, vol. 1776, p. 10 (2016)","DOI":"10.1063\/1.4965323"},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"Khachay, M., Ogorodnikov, Y.: PTAS for the Euclidean capacitated vehicle routing problem with time windows. In: International Conference on Learning and Intelligent Optimization (2019)","DOI":"10.1007\/978-3-030-38629-0_18"},{"issue":"2","key":"19_CR15","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1002\/net.3230110211","volume":"11","author":"JK Lenstra","year":"1981","unstructured":"Lenstra, J.K., Kan, A.R.: Complexity of vehicle routing and scheduling problems. Networks 11(2), 221\u2013227 (1981)","journal-title":"Networks"},{"key":"19_CR16","unstructured":"Liu, F., Lu, C., Gui, L., Zhang, Q., Tong, X., Yuan, M.: Heuristics for vehicle routing problem: a survey and recent advances. CoRR, abs\/2303.04147 (2023)"},{"issue":"2","key":"19_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3575799","volume":"19","author":"C Mathieu","year":"2023","unstructured":"Mathieu, C., Zhou, H.: A PTAS for capacitated vehicle routing on trees. ACM Trans. Algorithms 19(2), 1\u201328 (2023)","journal-title":"ACM Trans. Algorithms"},{"key":"19_CR18","doi-asserted-by":"crossref","unstructured":"Miltenburg, S., Oosterwijk, T., Sitters, R.: Complexity of fixed order routing. In: Approximation and Online Algorithms: 22nd International Workshop, WAOA 2024, Egham, UK, 5\u20136 September 2024, pp. 183\u2013197. Springer, Heidelberg (2025)","DOI":"10.1007\/978-3-031-81396-2_13"},{"key":"19_CR19","unstructured":"Sitters, R.: An $$n^{O(\\log \\log n)}$$ time approximation scheme for capacitated VRP in the Euclidean plane. CoRR, abs\/2507.15549 (2025)"},{"issue":"4","key":"19_CR20","doi-asserted-by":"publisher","first-page":"1217","DOI":"10.1007\/s10878-015-9931-5","volume":"32","author":"L Song","year":"2016","unstructured":"Song, L., Huang, H., Hongwei, D.: Approximation schemes for Euclidean vehicle routing problems with time windows. J. Comb. Optim. 32(4), 1217\u20131231 (2016)","journal-title":"J. Comb. Optim."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2026: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-17801-5_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:16Z","timestamp":1770918796000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-17801-5_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032178008","9783032178015"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-17801-5_19","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 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Krakow","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","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":"9 February 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 February 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"51","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sofsem.uj.edu.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}