{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:46:00Z","timestamp":1770993960835,"version":"3.50.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,3,10]],"date-time":"2023-03-10T00:00:00Z","timestamp":1678406400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"<jats:p>We give a polynomial time approximation scheme (PTAS) for the unit demand capacitated vehicle routing problem (CVRP) on trees, for the entire range of the tour capacity. The result extends to the splittable CVRP.<\/jats:p>","DOI":"10.1145\/3575799","type":"journal-article","created":{"date-parts":[[2022,12,14]],"date-time":"2022-12-14T12:15:47Z","timestamp":1671020147000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["A PTAS for Capacitated Vehicle Routing on Trees"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0517-112X","authenticated-orcid":false,"given":"Claire","family":"Mathieu","sequence":"first","affiliation":[{"name":"CNRS Paris, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1059-4909","authenticated-orcid":false,"given":"Hang","family":"Zhou","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique, IP Paris, Palaiseau, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,3,10]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054110007623"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.24.4.294"},{"key":"e_1_3_3_4_2","volume-title":"Models for Practical Routing Problems in Logistics","author":"Anbuudayasankar S. P.","year":"2016","unstructured":"S. P. Anbuudayasankar, K. Ganesh, and Sanjay Mohapatra. 2016. Models for Practical Routing Problems in Logistics. Springer."},{"issue":"2","key":"e_1_3_3_5_2","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1023\/A:1011461300596","article-title":"A new approximation algorithm for the capacitated vehicle routing problem on a tree","volume":"5","author":"Asano Tetsuo","year":"2001","unstructured":"Tetsuo Asano, Naoki Katoh, and Kazuhiro Kawashima. 2001. A new approximation algorithm for the capacitated vehicle routing problem on a tree. J. Combin. Optim. 5, 2 (2001), 213\u2013231.","journal-title":"J. Combin. Optim."},{"key":"e_1_3_3_6_2","first-page":"275","volume-title":"29th Annual ACM Symposium on Theory of Computing","author":"Asano Tetsuo","year":"1997","unstructured":"Tetsuo Asano, Naoki Katoh, Hisao Tamaki, and Takeshi Tokuyama. 1997. Covering points in the plane by k-tours: Towards a polynomial time approximation scheme for general k. In 29th Annual ACM Symposium on Theory of Computing. 275\u2013283."},{"key":"e_1_3_3_7_2","series-title":"LIPIcs","first-page":"3:1\u20133:15","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201918)","author":"Becker Amariah","year":"2018","unstructured":"Amariah Becker. 2018. A tight 4\/3 approximation for capacitated vehicle routing in trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201918)(LIPIcs, Vol. 116). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 3:1\u20133:15."},{"key":"e_1_3_3_8_2","volume-title":"25th Annual European Symposium on Algorithms (ESA\u201917)","author":"Becker Amariah","year":"2017","unstructured":"Amariah Becker, Philip N. Klein, and David Saulpic. 2017. A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs. In 25th Annual European Symposium on Algorithms (ESA\u201917). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_3_9_2","volume-title":"26th Annual European Symposium on Algorithms (ESA\u201918)","author":"Becker Amariah","year":"2018","unstructured":"Amariah Becker, Philip N. Klein, and David Saulpic. 2018. Polynomial-time approximation schemes for k-center, k-median, and capacitated vehicle routing in bounded highway dimension. In 26th Annual European Symposium on Algorithms (ESA\u201918). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_3_10_2","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/978-3-030-24766-9_8","volume-title":"Workshop on Algorithms and Data Structures","author":"Becker Amariah","year":"2019","unstructured":"Amariah Becker, Philip N. Klein, and Aaron Schild. 2019. A PTAS for bounded-capacity vehicle routing in planar graphs. In Workshop on Algorithms and Data Structures. Springer, 99\u2013111."},{"key":"e_1_3_3_11_2","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/978-3-030-24766-9_9","volume-title":"Workshop on Algorithms and Data Structures","author":"Becker Amariah","year":"2019","unstructured":"Amariah Becker and Alice Paul. 2019. A framework for vehicle routing approximation schemes in trees. In Workshop on Algorithms and Data Structures. Springer, 112\u2013125."},{"key":"e_1_3_3_12_2","first-page":"1","volume-title":"International Conference on Integer Programming and Combinatorial Optimization","author":"Blauth Jannis","year":"2021","unstructured":"Jannis Blauth, Vera Traub, and Jens Vygen. 2021. Improving the approximation ratio for capacitated vehicle routing. In International Conference on Integer Programming and Combinatorial Optimization. Springer, 1\u201314."},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2006.04.002"},{"key":"e_1_3_3_14_2","first-page":"589","volume-title":"IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS\u201920)","author":"Cohen-Addad Vincent","year":"2020","unstructured":"Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, and Hung Le. 2020. On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs. In IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS\u201920). IEEE, 589\u2013600."},{"key":"e_1_3_3_15_2","volume-title":"Fleet Management and Logistics","author":"Crainic Teodor G.","year":"2012","unstructured":"Teodor G. Crainic and Gilbert Laporte. 2012. Fleet Management and Logistics. Springer Science & Business Media."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.6.1.80"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9906-4"},{"key":"e_1_3_3_18_2","article-title":"Improved approximations for CVRP with unsplittable demands","author":"Friggstad Zachary","year":"2021","unstructured":"Zachary Friggstad, Ramin Mousavi, Mirmahdi Rahgoshay, and Mohammad R. Salavatipour. 2021. Improved approximations for CVRP with unsplittable demands. arXiv preprint arXiv:2111.08138 (2021).","journal-title":"arXiv preprint arXiv:2111.08138"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-77778-8"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110308"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.4.527"},{"key":"e_1_3_3_22_2","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/3-540-49381-6_42","volume-title":"International Symposium on Algorithms and Computation","author":"Hamaguchi Shin-ya","year":"1998","unstructured":"Shin-ya Hamaguchi and Naoki Katoh. 1998. A capacitated vehicle routing problem on a tree. In International Symposium on Algorithms and Computation. Springer, 399\u2013407."},{"key":"e_1_3_3_23_2","first-page":"877","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA\u201922)","author":"Jayaprakash Aditya","year":"2022","unstructured":"Aditya Jayaprakash and Mohammad R. Salavatipour. 2022. Approximation schemes for capacitated vehicle routing on graphs of bounded treewidth, bounded doubling, or highway dimension. In ACM-SIAM Symposium on Discrete Algorithms (SODA\u201922). 877\u2013893."},{"key":"e_1_3_3_24_2","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/978-3-319-44914-2_16","volume-title":"International Conference on Discrete Optimization and Operations Research","author":"Khachay Michael","year":"2016","unstructured":"Michael Khachay and Roman Dubinin. 2016. PTAS for the euclidean capacitated vehicle routing problem in \\(\\mathbb {R}^d\\) . In International Conference on Discrete Optimization and Operations Research. Springer, 193\u2013205."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.39.4.616"},{"key":"e_1_3_3_26_2","doi-asserted-by":"crossref","unstructured":"Claire Mathieu and Hang Zhou. 2022. A Tight  \\((1.5 + \\epsilon)\\) -Approximation for Unsplittable Capacitated Vehicle Routing on Trees. Retrieved from https:\/\/arxiv.org\/abs\/2202.05691.","DOI":"10.1145\/3575799"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718515"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3575799","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3575799","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:51:21Z","timestamp":1750182681000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3575799"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,10]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1145\/3575799"],"URL":"https:\/\/doi.org\/10.1145\/3575799","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,10]]},"assertion":[{"value":"2022-05-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-05","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}