PreprintCC BY-NC-ND 4.0arXiv
Improved Approximation for Unsplittable CVRP via a Greedy Approach
Abstract
We devise a polynomial-time $3.159$-approximation algorithm for the metric unsplittable Capacitated Vehicle Routing Problem. We build on the Relative Greedy Algorithm suggested by Traub (2025), which can be considered as a variant of the LP rounding algorithm of Friggstad, Mousavi, Rahgoshay, and Salavatipour (2025). Our main ingredient is the Average Greedy Algorithm, a new algorithm that controls both tour costs and the coverage of clients with high demand. This additional control enables a sharper averaging argument for the cost of subsequent greedy choices. Similarly to Zhao and Xiao (2026), combining the Average Greedy with variants of tour partitioning and a matching algorithm yields the final approximation guarantee.
Related
- The Price of Feasibility: Greedy Approximation Bounds for String Supermodular Optimization over Oracle-Conditioned Greedoids
- Improved Approximation Guarantees for Periodic-Review Stochastic Inventory Control
- Strong Edge Colouring of Disk Graphs: A 6-Approximation and an Improved Unit-Disk Bound
- A semi-greedy Markushevich basis which is not quasi-greedy
- Isometric Theory for Greedy-Type Properties with Enlarged Greedy Sums
BibTeX
@misc{ebert2026improved,
title = {{Improved Approximation for Unsplittable CVRP via a Greedy Approach}},
author = {Daniel Ebert and Leonard Weismantel},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.16910},
eprint = {2609.16910},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.16910},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Improved Approximation for Unsplittable CVRP via a Greedy Approach
AU - Daniel Ebert
AU - Leonard Weismantel
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.16910
UR - https://arxiv.org/abs/2609.16910
AB - We devise a polynomial-time $3.159$-approximation algorithm for the metric unsplittable Capacitated Vehicle Routing Problem. We build on the Relative Greedy Algorithm suggested by Traub (2025), which can be considered as a variant of the LP rounding algorithm of Friggstad, Mousavi, Rahgoshay, and Salavatipour (2025). Our main ingredient is the Average Greedy Algorithm, a new algorithm that controls both tour costs and the coverage of clients with high demand. This additional control enables a sharper averaging argument for the cost of subsequent greedy choices. Similarly to Zhao and Xiao (2026), combining the Average Greedy with variants of tour partitioning and a matching algorithm yields the final approximation guarantee.
ER -