{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T05:58:07Z","timestamp":1777874287591,"version":"3.51.4"},"reference-count":57,"publisher":"Elsevier BV","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.elsevier.com\/tdm\/userlicense\/1.0\/"},{"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.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62502078"],"award-info":[{"award-number":["62502078"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62372095"],"award-info":[{"award-number":["62372095"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[2026,1]]},"DOI":"10.1016\/j.ic.2026.105405","type":"journal-article","created":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T16:10:15Z","timestamp":1768320615000},"page":"105405","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Improved approximations for the capacitated vehicle routing problem with fixed capacity"],"prefix":"10.1016","volume":"308","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2322-750X","authenticated-orcid":false,"given":"Jingyang","family":"Zhao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1012-2373","authenticated-orcid":false,"given":"Mingyu","family":"Xiao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"issue":"1","key":"10.1016\/j.ic.2026.105405_br0010","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","article-title":"The truck dispatching problem","volume":"6","author":"Dantzig","year":"1959","journal-title":"Manag. Sci."},{"key":"10.1016\/j.ic.2026.105405_br0020","series-title":"Vehicle Routing: Problems, Methods, and Applications","author":"Toth","year":"2014"},{"issue":"4","key":"10.1016\/j.ic.2026.105405_br0030","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/j.disopt.2006.04.002","article-title":"Improved bounds for vehicle routing solutions","volume":"3","author":"Bompadre","year":"2006","journal-title":"Discrete Optim."},{"issue":"2","key":"10.1016\/j.ic.2026.105405_br0040","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s10107-022-01841-4","article-title":"Improving the approximation ratio for capacitated vehicle routing","volume":"197","author":"Blauth","year":"2023","journal-title":"Math. Program."},{"key":"10.1016\/j.ic.2026.105405_br0050","series-title":"49th International Colloquium on Automata, Languages, and Programming","first-page":"95:1","article-title":"A PTAS for capacitated vehicle routing on trees","volume":"vol. 229","author":"Mathieu","year":"2022"},{"key":"10.1016\/j.ic.2026.105405_br0060","series-title":"50th International Colloquium on Automata, Languages, and Programming","first-page":"91:1","article-title":"A tight (1.5+\u03b5)-approximation for unsplittable capacitated vehicle routing on trees","volume":"vol. 261","author":"Mathieu","year":"2023"},{"key":"10.1016\/j.ic.2026.105405_br0070","series-title":"61st IEEE Annual Symposium on Foundations of Computer Science","first-page":"589","article-title":"On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs","author":"Cohen-Addad","year":"2020"},{"key":"10.1016\/j.ic.2026.105405_br0080","series-title":"63rd IEEE Annual Symposium on Foundations of Computer Science","first-page":"1081","article-title":"Low treewidth embeddings of planar and minor-free metrics","author":"Filtser","year":"2022"},{"key":"10.1016\/j.ic.2026.105405_br0090","series-title":"Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing","first-page":"275","article-title":"Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k","author":"Asano","year":"1997"},{"key":"10.1016\/j.ic.2026.105405_br0100","series-title":"Covering points in the plane by k-tours: a polynomial approximation scheme for fixed k","author":"Asano","year":"1996"},{"issue":"4","key":"10.1016\/j.ic.2026.105405_br0110","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1287\/moor.10.4.527","article-title":"Bounds and heuristics for capacitated routing problems","volume":"10","author":"Haimovich","year":"1985","journal-title":"Math. Oper. Res."},{"issue":"4","key":"10.1016\/j.ic.2026.105405_br0120","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0167-6377(87)90012-5","article-title":"Heuristics for unequal weight delivery problems with a fixed error guarantee","volume":"6","author":"Altinkemer","year":"1987","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"10.1016\/j.ic.2026.105405_br0130","doi-asserted-by":"crossref","DOI":"10.1007\/s43069-021-00101-z","article-title":"Worst-case analysis of a new heuristic for the travelling salesman problem","volume":"3","author":"Christofides","year":"2022","journal-title":"Oper. Res. Forum"},{"key":"10.1016\/j.ic.2026.105405_br0140","first-page":"76","article-title":"Some extremal bypasses in graphs","volume":"17","author":"Serdyukov","year":"1978","journal-title":"Upr. Sist."},{"key":"10.1016\/j.ic.2026.105405_br0150","series-title":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","first-page":"32","article-title":"A (slightly) improved approximation algorithm for metric TSP","author":"Karlin","year":"2021"},{"key":"10.1016\/j.ic.2026.105405_br0160","series-title":"Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Madison, WI, USA, June 21-23, 2023, Proceedings","first-page":"261","article-title":"A deterministic better-than-3\/2 approximation algorithm for metric TSP","volume":"vol. 13904","author":"Karlin","year":"2023"},{"key":"10.1016\/j.ic.2026.105405_br0170","series-title":"32nd International Symposium on Algorithms and Computation","first-page":"43:1","article-title":"Probabilistic analysis of Euclidean capacitated vehicle routing","volume":"vol. 212","author":"Mathieu","year":"2021"},{"key":"10.1016\/j.ic.2026.105405_br0180","series-title":"Integer Programming and Combinatorial Optimization - 23rd International Conference, IPCO 2022, Eindhoven, the Netherlands, June 27-29, 2022, Proceedings","first-page":"251","article-title":"Improved approximations for capacitated vehicle routing with unsplittable client demands","volume":"vol. 13265","author":"Friggstad","year":"2022"},{"issue":"6","key":"10.1016\/j.ic.2026.105405_br0190","doi-asserted-by":"crossref","first-page":"654","DOI":"10.1002\/(SICI)1520-6750(199909)46:6<654::AID-NAV4>3.0.CO;2-A","article-title":"Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries","volume":"46","author":"Anily","year":"1999","journal-title":"Nav. Res. Logist."},{"issue":"4","key":"10.1016\/j.ic.2026.105405_br0200","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0020-0190(00)00097-1","article-title":"Better approximations for max TSP","volume":"75","author":"Hassin","year":"2000","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"10.1016\/j.ic.2026.105405_br0210","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.dam.2004.07.003","article-title":"Approximation algorithms for some vehicle routing problems","volume":"146","author":"Bazgan","year":"2005","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.ic.2026.105405_br0220","series-title":"Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings","first-page":"173","article-title":"A 4\/5 - approximation algorithm for the maximum traveling salesman problem","volume":"vol. 10328","author":"Dudycz","year":"2017"},{"issue":"3","key":"10.1016\/j.ic.2026.105405_br0230","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","article-title":"A greedy heuristic for the set-covering problem","volume":"4","author":"Chv\u00e1tal","year":"1979","journal-title":"Math. Oper. Res."},{"issue":"1","key":"10.1016\/j.ic.2026.105405_br0240","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1137\/S0097539704444750","article-title":"A better-than-greedy approximation algorithm for the minimum set cover problem","volume":"35","author":"Hassin","year":"2005","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.ic.2026.105405_br0250","series-title":"2023 Symposium on Simplicity in Algorithms","first-page":"1","article-title":"A local search-based approach for set covering","author":"Gupta","year":"2023"},{"issue":"6","key":"10.1016\/j.ic.2026.105405_br0260","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1287\/inte.13.6.4","article-title":"Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer","volume":"13","author":"Bell","year":"1983","journal-title":"Interfaces"},{"issue":"3","key":"10.1016\/j.ic.2026.105405_br0270","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1016\/j.ejor.2016.08.012","article-title":"New benchmark instances for the capacitated vehicle routing problem","volume":"257","author":"Uchoa","year":"2017","journal-title":"Eur. J. Oper. Res."},{"issue":"6","key":"10.1016\/j.ic.2026.105405_br0280","doi-asserted-by":"crossref","first-page":"893","DOI":"10.1142\/S0129054110007623","article-title":"Ptas for k-tour cover problem on the plane for moderately large values of k","volume":"21","author":"Adamaszek","year":"2010","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10.1016\/j.ic.2026.105405_br0290","series-title":"Discrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Vladivostok, Russia, September 19-23, 2016, Proceedings","first-page":"193","article-title":"PTAS for the Euclidean capacitated vehicle routing problem in R\u0302d","volume":"vol. 9869","author":"Khachay","year":"2016"},{"issue":"1","key":"10.1016\/j.ic.2026.105405_br0300","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s00453-014-9906-4","article-title":"A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing","volume":"73","author":"Das","year":"2015","journal-title":"Algorithmica"},{"key":"10.1016\/j.ic.2026.105405_br0310","series-title":"Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms","first-page":"877","article-title":"Approximation schemes for capacitated vehicle routing on graphs of bounded treewidth, bounded doubling, or highway dimension","author":"Jayaprakash","year":"2022"},{"key":"10.1016\/j.ic.2026.105405_br0320","series-title":"25th Annual European Symposium on Algorithms","first-page":"12:1","article-title":"A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs","volume":"vol. 87","author":"Becker","year":"2017"},{"key":"10.1016\/j.ic.2026.105405_br0330","series-title":"26th Annual European Symposium on Algorithms","first-page":"8:1","article-title":"Polynomial-time approximation schemes for k-center, k-median, and capacitated vehicle routing in bounded highway dimension","volume":"vol. 112","author":"Becker","year":"2018"},{"key":"10.1016\/j.ic.2026.105405_br0340","series-title":"Algorithms and Data Structures - 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings","first-page":"99","article-title":"A PTAS for bounded-capacity vehicle routing in planar graphs","volume":"vol. 11646","author":"Becker","year":"2019"},{"key":"10.1016\/j.ic.2026.105405_br0350","series-title":"64th IEEE Annual Symposium on Foundations of Computer Science","first-page":"2262","article-title":"Planar and minor-free metrics embed into metrics of polylogarithmic treewidth with expected multiplicative distortion arbitrarily close to 1","author":"Cohen-Addad","year":"2023"},{"issue":"4","key":"10.1016\/j.ic.2026.105405_br0360","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1287\/opre.39.4.616","article-title":"Capacitated vehicle routing on trees","volume":"39","author":"Labb\u00e9","year":"1991","journal-title":"Oper. Res."},{"issue":"3","key":"10.1016\/j.ic.2026.105405_br0370","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1002\/net.3230110308","article-title":"Capacitated arc routing problems","volume":"11","author":"Golden","year":"1981","journal-title":"Networks"},{"key":"10.1016\/j.ic.2026.105405_br0380","series-title":"Algorithms and Computation, 9th International Symposium, ISAAC '98, Taejon, Korea, December 14-16, 1998, Proceedings","first-page":"397","article-title":"A capacitated vehicle routing problem on a tree","volume":"vol. 1533","author":"Hamaguchi","year":"1998"},{"issue":"2","key":"10.1016\/j.ic.2026.105405_br0390","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","year":"2001","journal-title":"J. Comb. Optim."},{"key":"10.1016\/j.ic.2026.105405_br0400","series-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","first-page":"3:1","article-title":"A tight 4\/3 approximation for capacitated vehicle routing in trees","volume":"vol. 116","author":"Becker","year":"2018"},{"key":"10.1016\/j.ic.2026.105405_br0410","series-title":"Algorithms and Data Structures - 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings","first-page":"112","article-title":"A framework for vehicle routing approximation schemes in trees","volume":"vol. 11646","author":"Becker","year":"2019"},{"key":"10.1016\/j.ic.2026.105405_br0420","series-title":"14th Innovations in Theoretical Computer Science Conference","first-page":"63:1","article-title":"Unsplittable Euclidean capacitated vehicle routing: a (2+\u03b5)-approximation algorithm","volume":"vol. 251","author":"Grandoni","year":"2023"},{"key":"10.1016\/j.ic.2026.105405_br0430","series-title":"40th International Symposium on Theoretical Aspects of Computer Science","first-page":"27:1","article-title":"An approximation algorithm for distance-constrained vehicle routing on trees","volume":"vol. 254","author":"Dufay","year":"2023"},{"key":"10.1016\/j.ic.2026.105405_br0440","series-title":"2023 Symposium on Simplicity in Algorithms","first-page":"114","article-title":"Capacitated vehicle routing in graphic metrics","author":"M\u00f6mke","year":"2023"},{"issue":"4","key":"10.1016\/j.ic.2026.105405_br0450","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1287\/trsc.24.4.294","article-title":"Heuristics for delivery problems with constant error guarantees","volume":"24","author":"Altinkemer","year":"1990","journal-title":"Transp. Sci."},{"key":"10.1016\/j.ic.2026.105405_br0460","series-title":"Extensions of matching theory","author":"Hartvigsen","year":"1984"},{"key":"10.1016\/j.ic.2026.105405_br0470","series-title":"Combinatorial Optimization: Polyhedra and Efficiency, vol. 24","author":"Schrijver","year":"2003"},{"issue":"3","key":"10.1016\/j.ic.2026.105405_br0480","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1002\/nav.3800370304","article-title":"Split delivery routing","volume":"37","author":"Dror","year":"1990","journal-title":"Nav. Res. Logist."},{"key":"10.1016\/j.ic.2026.105405_br0490","series-title":"Implementation of algorithms for maximum matching on nonbipartite graphs","author":"Gabow","year":"1974"},{"key":"10.1016\/j.ic.2026.105405_br0500","series-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler","year":"1976"},{"issue":"6","key":"10.1016\/j.ic.2026.105405_br0510","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","article-title":"Shortest connection networks and some generalizations","volume":"36","author":"Prim","year":"1957","journal-title":"Bell Syst. Tech. J."},{"issue":"1","key":"10.1016\/j.ic.2026.105405_br0520","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1145\/505241.505243","article-title":"An optimal minimum spanning tree algorithm","volume":"49","author":"Pettie","year":"2002","journal-title":"J. ACM"},{"key":"10.1016\/j.ic.2026.105405_br0530","series-title":"Proceedings of the 10th Annual ACM Symposium on Theory of Computing","first-page":"240","article-title":"On the completeness of a generalized matching problem","author":"Kirkpatrick","year":"1978"},{"issue":"2","key":"10.1016\/j.ic.2026.105405_br0540","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1137\/S0097539793242618","article-title":"A general approximation technique for constrained forest problems","volume":"24","author":"Goemans","year":"1995","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10.1016\/j.ic.2026.105405_br0550","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0020-0190(97)00097-5","article-title":"An approximation algorithm for maximum packing of 3-edge paths","volume":"63","author":"Hassin","year":"1997","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"10.1016\/j.ic.2026.105405_br0560","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1287\/ijoc.2.1.64","article-title":"Worst-case analysis of heuristics for multidepot capacitated vehicle routing problems","volume":"2","author":"Li","year":"1990","journal-title":"INFORMS J. Comput."},{"key":"10.1016\/j.ic.2026.105405_br0570","series-title":"50th International Symposium on Mathematical Foundations of Computer Science","first-page":"93:1","article-title":"Improved approximation algorithms for capacitated vehicle routing with fixed capacity","volume":"vol. 345","author":"Zhao","year":"2025"}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540126000039?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540126000039?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T19:30:07Z","timestamp":1777577407000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0890540126000039"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1]]},"references-count":57,"alternative-id":["S0890540126000039"],"URL":"https:\/\/doi.org\/10.1016\/j.ic.2026.105405","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[2026,1]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Improved approximations for the capacitated vehicle routing problem with fixed capacity","name":"articletitle","label":"Article Title"},{"value":"Information and Computation","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.ic.2026.105405","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"105405"}}