Improving the Approximation Ratio for Capacitated Vehicle Routing
Not on the map. Why?
Abstract (arXiv)
We devise a new approximation algorithm for capacitated vehicle routing. Our algorithm yields a better approximation ratio for general capacitated vehicle routing as well as for the unit-demand case and the splittable variant. Our results hold in arbitrary metric spaces. This is the first improvement upon the classical tour partitioning algorithm by Haimovich and Rinnooy Kan and Altinkemer and Gavish.
Key facts. Cited by 1 paper in the map (data through 13 Oct 2026). First posted on arXiv 10 Nov 2020.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2026: 1.
1 paper.