Source-linked AI summary
Improved Approximation for Unsplittable CVRP via a Greedy Approach
Daniel Ebert, Leonard Weismantel
TL;DR
Metric unsplittable CVRP asks for minimum-cost depot tours serving every client exactly once within each tour’s capacity. The paper combines an Average Greedy algorithm with tour partitioning and matching, achieving a polynomial-time approximation below α + 1.659, or 3.159 in the symmetric case.
Problem
Metric unsplittable CVRP requires minimum-cost depot tours that serve every client exactly once while keeping each tour’s total demand at most one; prior work had a guarantee below 3.176.
Source: §1 · p. 1Method
The Average Greedy Algorithm controls tour cost and coverage of high-demand clients, and is combined with tour partitioning and a matching algorithm.
Source: §2 · p. 6, §4 · p. 18Results
3.159 in the symmetric case, from a polynomial-time (α + 1.659)-approximation for CVRP.
Source: §1 · p. 2Takeaways & Limitations
The improved approximation applies to both symmetric and asymmetric cost functions.
Source: §1 · p. 2The analysis assumes correct guesses for r̃b(Vsingle) in a fixed instantiation of Algorithm 3.
Source: §2 · p. 9
Abstract
from arXiv · showhide
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.
1 Introduction
The introduction frames metric unsplittable CVRP and presents an improved approximation based on greedy tour selection, strengthened by coverage guarantees for clients with high demand.
1 Introduction
- Below α + 1.659 (3.159 in the symmetric case), the polynomial-time algorithm improves on the prior guarantee of below 3.176.The theorem states the general approximation guarantee; the paper gives the symmetric-case value and prior comparison.Source: §1 · pp. 1–2
- The Average Greedy Algorithm retains Traub’s cost bound while guaranteeing lower bounds on selected high-demand clients, enabling sharper averaging.The introduction identifies high-demand coverage as necessary for improving the approximation ratio.Source: §1 · p. 2
1.1 Preliminaries
- The δ-ITP routine serves clients W at cost at most α · OPT + σδ(W), while Relative Greedy combines it with an initial phase for clients of demand at least δ.Source: §1.1 · p. 3
1.2 The Matching Savings Algorithm
- Matching Savings uses a maximum-weight matching on feasible client pairs and guarantees either a sufficiently good solution or an instance with many single clients.The graph joins clients whose combined demand is at most one.Source: §1.2 · p. 5
2 Average Greedy Algorithm
The Average Greedy Algorithm extends the Relative Greedy Algorithm with guarantees on the number of selected clients with large demand. It uses those guarantees to sharpen the averaging bound on later greedy choices.
2 Average Greedy Algorithm
- Selected large-demand clients can make their optimum tours less efficient, so excluding those tours from the average can improve the cost bound.The algorithm seeks a subset of selected clients whose bucket masses support the improved bound.Source: §2 · pp. 6–7
- The algorithm tracks bucketed coverage of single clients with large demand while controlling the cost-to-potential ratios of selected tours.It uses a one-sided discrepancy measure to track unfavorable deviations from cost and bucket-mass targets.Source: §2 · pp. 7, 9
- The coverage guarantees apply to single clients, not necessarily to a partner sharing an optimum tour; instances with many double clients can instead yield a good solution from Algorithm 2.The stated caveat concerns serving the partner while retaining the improved cost bound.Source: §2 · p. 7
- At the end of the greedy phase, tours whose cost exceeds their potential are dissolved, and δ-ITP serves their clients along with the remaining small-demand clients.The stated additional cost for dissolving such a tour is at most its potential.Source: §2 · pp. 8–9
3 Cost Density Functions
The section derives two valid cost density functions for bounding the cost of Algorithm 3. These yield separate cost bounds for the cases δ = η and δ = 1/3.
3 Cost Density Functions
- Two cost density functions are derived, each intended to bound the greedy choices and thereby provide a cost bound for Algorithm 3.The section states that the remaining validity conditions follow from computation and are checked separately.Source: §3 · pp. 14, 15, 17
- For δ = η, Algorithm 3 has solution cost at most Cη.The corollary defines Cη, but its formula is not present in the supplied passage.Source: §3 · p. 17
- Corollary 2 states that the solution obtained by Algorithm 3 with δ = 1/3 has cost at most C1/3.Source: §3 · p. 17
4 Deriving the Approximation Ratio
The section proves a polynomial-time approximation guarantee by comparing a matching algorithm with two Average Greedy variants and returning the cheapest solution. An interval-arithmetic certificate establishes the bound.
4 Deriving the Approximation Ratio
- The analysis compares Matching Savings with Average Greedy using potentials ση and σ1/3, then returns the cheapest of the three solutions.For every instance, at least one of the three cost bounds is at most (α + 1.659)OPT.Source: §4 · p. 18
- The cheapest of the matching and two Average Greedy solutions achieves the claimed (α + 1.659)OPT approximation bound.The theorem proof fixes sufficiently small ϵ and η and applies the three-bound guarantee.Source: §4 · p. 18
- For fixed ϵ and η, Average Greedy examines n^O(1/η) candidate tours over at most n iterations, giving polynomial runtime.The runtime argument also uses a constant number of copies and guess vectors in the stated reduction.Source: §4 · p. 18
- Interval arithmetic certifies the Average Greedy cost-bound maximum is strictly below ρ = α + 1.659 over a three-dimensional prism.The proof simplifies the bounds, reduces a six-dimensional problem to a three-dimensional prism, then certifies the upper bound.Source: §4 · pp. 18, 22
A Proof of Lemma 1
The proof builds feasible CVRP tours by splitting an approximate TSP tour, accounting for singleton clients and expected reconnection costs. Optimal dynamic programming makes the resulting bound deterministic.
A Proof of Lemma 1
- The algorithm first serves clients with demand greater than 1/2 by singleton tours, then computes an α-approximate TSP tour and splits it using a uniform random offset.Split segments are connected to the depot to form feasible tours.Source: A Proof of Lemma 1 · p. 24
- Clients with demand at most δ always fit the previous segment, while clients in V1/2 have a stated conditional fit probability that determines their expected connection cost.The proof sums the resulting expected connection costs over the respective client sets.Source: A Proof of Lemma 1 · p. 24
- The TSP cost, splitting cost, and singleton-tour cost combine into the claimed bound, and optimal dynamic programming makes tour splitting deterministic.The cost bound therefore holds deterministically.Source: A Proof of Lemma 1 · p. 24
B Reduction to Small Tours
The reduction constructs a replicated instance by copying the original and identifying depots. Solutions transfer between the instances with controlled total cost, so solving the replicated instance suffices.
B Reduction to Small Tours
- The reduction makes C = ⌈1/(ϵη)⌉ copies of the instance and identifies their depot vertices, using metric closure between clients in different copies.The lemma’s premise includes an added upper bound on R1(T) for each tour.Source: B Reduction to Small Tours · pp. 24–25
- Copying each tour of a solution to the original instance C times gives a solution to the replicated instance costing at most C times as much.The copies use the same depot.Source: B Reduction to Small Tours · p. 25
- A solution to the replicated instance can be subdivided at copy boundaries into C solutions to the original instance with total cost no greater, so solving the replicated instance suffices.The metric closure permits subdivision without increasing cost.Source: B Reduction to Small Tours · p. 25
C Proof of Lemma 10
The proof checks continuity and monotonicity of the fractional expressions used in the lemma. It handles the minimum and maximum construction by verifying its component fractions on the regions where they attain the minimum.
C Proof of Lemma 10
- The proof establishes continuity for Φ formed from minima and maxima of two fractional expressions and 1 by checking the fractions where they attain the minimum.Taking minima and maxima preserves continuity once the component conditions hold.Source: C Proof of Lemma 10 · p. 25
- A lower bound on the denominator supports the continuity check by keeping the fractional expressions’ denominators positive.The proof derives a lower bound on D before establishing the continuity condition.Source: C Proof of Lemma 10 · p. 26
- For monotonicity, increasing t subtracts from the numerator and denominator at rates bounded so the fraction cannot decrease.The proof compares those changes using bounds involving OPT and σδ(V1η).Source: C Proof of Lemma 10 · p. 26