{"id":"arxiv/2609.16910","url":"https://arxiv.org/abs/2609.16910","tags":["cs.DS","math.CO"],"score":0,"title":"Improved Approximation for Unsplittable CVRP via a Greedy Approach","domain":"cs.DS","source":"arxiv","authors":["Daniel Ebert","Leonard Weismantel"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-15","reactions":{}}