Improved Approximation for Unsplittable CVRP via a Greedy Approach
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.16910
curl -X POST /api/v1/records/arxiv/2609.16910/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.16910/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'