Source-linked AI summary
A (Slightly) Improved Approximation Algorithm for Metric TSP
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
TL;DR
Metric TSP remains difficult to approximate closely despite the triangle inequality and an NP-hardness barrier. This paper develops a randomized approach and proves a 3/2 − ε approximation for some ε > 10^-36, while noting that the tiny improvement results from a restrictive proof parameter.
Problem
Metric TSP studies minimum-cost Hamiltonian cycles when distances satisfy the triangle inequality, against an NP-hardness barrier for approximation.
Method
The paper uses randomized constructions and reductions involving polygon structures, max-flow conditioning, and specialized criteria for handling edge bundles.
Results
For some ε > 10^-36, a randomized algorithm outputs a tour with expected cost at most 3/2 − ε times optimum.
Takeaways & Limitations
The result gives a very slightly improved randomized approximation guarantee for metric TSP.
Takeaways & Limitations
The proof requires 28η ≪ ε, forcing η to be very small and yielding only a very slightly improved approximation; it also does not improve the integrality-gap upper bound.
Abstract
from arXiv · showhide
For some $ε> 10^{-36}$ we give a randomized $3/2-ε$ approximation algorithm for metric TSP.
1 Introduction
Metric TSP remains difficult to approximate, with Christofides-Serdyukov’s 3/2 ratio still best known for the general case. This paper gives a randomized 3/2−ε approximation for metric TSP and develops new structural and probabilistic tools behind it.
- Problem: Metric TSP asks for a minimum-cost Hamiltonian cycle under symmetric distances satisfying the triangle inequality.For general distances, TSP is NP-hard to approximate within any polynomial factor.
- Context: 3/2 remains the best known approximation ratio for general metric TSP before this slight improvement.The benchmark is the Christofides-Serdyukov algorithm, despite extensive subsequent work.
- Limitations: The authors do not prove that the Held-Karp integrality gap is bounded away from 3/2, and their use of OPT edges prevents a new upper bound on that gap.The constraint 28η≪ε forces η to be very small, explaining the extremely small improvement.
- Algorithm: The algorithm samples a spanning tree whose edge marginals approximately match a Held-Karp relaxation, then adds a minimum-cost matching on odd-degree vertices.The resulting multigraph is converted to a Hamiltonian cycle using the triangle inequality.
- Structural tools: The proof reduces near-minimum-cut structure to polygon and hierarchy representations, including a special polygon family with no atom mapped inside.For adjacent atoms in this family, the paper establishes structural edge-weight bounds up to O(η).
- Probabilistic tools: The paper generalizes a strongly Rayleigh probability lemma: bounded probabilities for subset-sum events imply a lower bound on simultaneous target counts independent of the support size n.The proof has double-exponential dependence on ε, and improving that dependence remains open.
2 Preliminaries
The preliminaries establish the graph, cut, spanning-tree, and join-polytope framework, then develop strongly Rayleigh and λ-uniform spanning-tree distributions used in the analysis. The algorithm’s central challenge is constructing a random vector satisfying all cuts while achieving an expected cost below (1/2 − ε)OPT.
- Graph and cut notation: The paper models G = (V, E, x) with distinguished vertices and defines η-near minimum cuts by x(δ(S)) ≤ 2 + η.Cuts exclude the distinguished vertices unless stated otherwise, and crossing sets have all four basic regions non-empty.
- Spanning-tree framework: The spanning tree polytope is the convex hull of spanning-tree incidence vectors, and Held-Karp solutions restricted to E provide feasible points in this polytope.A zero-cost auxiliary edge converts the Held-Karp solution into a spanning-tree-polytope point while preserving the relevant cost identity.
- O-joins and satisfied cuts: The O-join polytope characterizes minimum-weight joins on the odd vertices of a spanning tree, supporting the matching-cost analysis.The paper defines satisfied cuts as a condition used when constructing the correction vector for the sampled tree.
- Algorithmic goal: The main algorithmic challenge is constructing a random vector y that satisfies all cuts and has expected cost at most (1/2 − ε)OPT.This target is the bridge between the spanning-tree sample and the final metric-TSP approximation analysis.
- Strongly Rayleigh distributions: Strongly Rayleigh distributions are closed under projection, conditioning, truncation, and products, while λ-uniform spanning-tree distributions form a strongly Rayleigh subclass.These closure operations are repeatedly applied in the paper, including edge conditioning and tree conditioning.
- Dependence and conditioning: Strongly Rayleigh distributions provide negative association and stochastic-dominance tools for controlling edge counts and conditional probabilities.For λ-uniform distributions, conditioning on a set being a tree yields an independence property between the tree inside that set and the contracted remainder.
3 Overview of Proof
The proof improves the Christofides-style bound by constructing a random slack vector whose expected reductions outweigh increases on cuts of a hierarchy, then extending this to all relevant near-minimum cuts. The resulting analysis yields a randomized 3/2 − 3 · 10^-36 approximation, while requiring extremely small parameters and using OPT edges.
- Proof strategy: The proof targets an O-join of expected cost at most OPT(1/2 − ε) by constructing a cheap feasible slack-based solution.This improves on the baseline xe/2 construction by exploiting cuts that are even in the sampled tree.
- Proof strategy: The algorithm starts with ye := xe/2 and modifies it using a random slack vector that reduces selected edges and compensates on other odd cuts.The construction seeks negative expected slack for LP edges while preserving feasibility.
- Theorem 3.1: The main technical theorem constructs slack vectors s and s* that satisfy every odd η-near-min-cut and maintain controlled expected slack on OPT edges.The theorem combines hierarchy-based slack with nonnegative OPT-edge slack whose expected per-edge cost is O(η^2).
- Final bound: 3/2 − 3 · 10^-36 is the resulting approximation factor, obtained after choosing β = η/4.1 = ε_P/5362.8.The proof requires 28η ≪ ε, forcing η to be very small and producing only a very slight improvement.
- Theorem 3.2: The payment theorem guarantees nonnegative slack on unhappy hierarchy cuts and negative expected slack for every LP edge other than e0.For each LP edge e ≠ e0, the expected slack is at most −βε_Px_e.
- Hierarchy and parity: The hierarchy analysis shows that triangle and polygon structure gives useful parity events, including a probability at most 1 − O(ε) for a relevant cut to remain odd after reduction.These parity properties support reductions whose expected savings exceed their compensating increases.
4 Polygons and the Hierarchy of Near Minimum Cuts
The section develops polygon and hierarchy structure for near-minimum cuts, then uses that structure to construct slack vectors that preserve cut feasibility while achieving negative expected slack on good edges.
- Polygon structure: Adjacent atoms in a polygon carry LP edge mass at least 1 −ǫη, while each atom and polygon cut remains near-minimum.The bounds are x(δ(ai)) ≤2 + 14η for atoms and x(δ(a1 ∪· · · ∪am−1)) ≤2 + 4η for polygon prefixes.
- One-sided crossings: For polygons crossed on one side, happy polygons and non-extreme cuts obtain the same cut-feasibility guarantee through OPT-edge slack.The theorem applies to arbitrary spanning-tree distributions with marginals x and handles cuts in the associated component.
- Hierarchy consequences: The hierarchy supplies enough good-edge mass near degree cuts and nonnegative slack for odd cuts whose parent is not a polygon cut.For every such degree-parent cut, x(Eg ∩δ(S)) ≥3/4.
- Slack construction: Theorem 4.6 constructs good edges and slack functions so odd near-minimum cuts satisfy s(δ(S)) + s∗(δ(S)) ≥0.For good edges, se ≥−xeβ and E[se] ≤−ǫPβxe; non-good edges receive zero slack.
5 Probabilistic statements
This section develops probabilistic tools for strongly Rayleigh distributions, including bounds for conditioned counts and applications to preserving edge marginals and parity events. It also establishes the local probabilistic guarantees used for good-edge constructions.
- Strongly Rayleigh distributions: Proposition 5.1 bounds the probability that all disjoint-set counts equal their targets after conditioning on the total count.Its proof decomposes the joint event into sequential conditional probabilities and applies the two-variable conditioning lemmas.
- Limitations: The resulting lower bound f(ε) is not tight, with the paper expecting exponential rather than doubly exponential dependence on the number of sets.The authors leave finding a tight lower bound as an open problem.
- Conditioning lemmas: Conditioning on a fixed combined count preserves one-sided probability bounds for the component counts through inequalities (18) and (19).Lemma 5.4 derives these bounds from negative association and stochastic dominance.
- Applications: Conditioning on a max-flow event can preserve all marginals in two sets up to total variation distance ζ while the event has constant probability.The construction uses a flow to distribute conditioned trees across pairs of edges while retaining their marginal probabilities approximately.
6 Matching
This section constructs a matching from good internal edge bundles to higher incident edges. The matching balances fractional edge mass under explicit parameter conditions and supports the paper’s slack-payment argument.
- Matching construction: The Matching Lemma maps good edge bundles inside a hierarchical cut to fractions of higher edges incident to their endpoint atoms.For each good bundle e=(u,v), the matching assigns fractions me,u and me,v of edges in δ↑(u) and δ↑(v).
- Matching construction: The matching avoids bad edges and uses parameters Fu and Zu to compensate for insufficient good-edge mass and parity-fixing burdens.Zu allows twice as many edges to be matched when x(δ↑(u)) is small.
- Notation: The notation distinguishes upward edge bundles from full cut edges, since δ→(W) includes bundles between atoms in W.This distinction is used throughout the matching and max-flow construction.
- Flow proof: When a hierarchical cut has three atoms, all internal edges are good and the required flow capacity follows from the fractional edge bounds.The proof derives c(s)≥2+εη for α≥2εη.
- Flow proof: For larger atom sets, at most half the edges are bad, allowing the cut-capacity argument to establish the required flow bound.The argument relies on there being at most one bad half edge adjacent to every vertex.
- Flow proof: For four atoms with zero or one bad edge, the good-edge mass is sufficient to meet the sink capacity under the stated parameter bounds.The proof uses xG≥2.5−εη/2−ε1/2 and assumes εF≤0.1, α≥2εη, and ε1/2≤0.01.
7 Reduction and payment
Section 7 defines reduction and increase events over top and bottom edge bundles, then proves the payment theorem’s structural and expected-slack guarantees under a maximum-entropy spanning-tree distribution.
- Event construction: The construction uses edge bundles, happy events, and uniformly subsampled events of probability exactly p to define decrease events.Happy events such as 2-1-1 and 2-2-2 occur with probability at least p; subsampling makes the corresponding decrease event occur with probability exactly p.
- Increase construction: The increase vector assigns bottom-edge increases according to whether polygon cuts are left-happy, right-happy, or happy, and top-edge increases using matchings and oddness indicators.For bottom bundles, the construction uses r(A), r(B), and r(C); for top bundles, it combines endpoint-specific indicators from a matching.
- Expected payment bounds: Theorem 7.1 bounds expected increases for good top and bottom bundles, yielding the bottom-edge estimate E [se] ≤−0.00006pβxe.The stated top-edge bound is E [Ie] ≤(1 −ǫ1/1)pτxe, while bottom bundles satisfy E [IS] ≤0.99994βp.
- Main payment theorem: For non-polygon-parent cuts, odd tree degree implies nonnegative total slack, while each good edge satisfies E [se] ≤−ǫPβxe.The edgewise expectation guarantee is the theorem’s principal payment property for good edges.
- Proof ingredients: The proof controls marginal changes caused by conditioning on near-minimum cuts or atoms, with overall change bounded by ±ǫη/2.Top-edge analysis relies on independence of tree sampling inside endpoint atoms from the reduction event and on Lemmas 7.2 and 7.7.
A Proofs from Section 5
Section 5 proves that several configurations of top edge bundles are happy or good with probabilities bounded below by expressions in ǫ1/2. The arguments condition on tree events, control expected edge counts, and apply correlation and concentration lemmas.
- Lemma 5.21: 0.005ǫ2 1/2 lower-bounds the probability that a sufficiently light top edge bundle is 2-1-1 happy.This is Lemma 5.21 for xe ≤1/2 −ǫ1/2 and ǫ1/2 ≤0.001.
- Lemma 5.22: 0.006ǫ2 1/2 lower-bounds the probability that a sufficiently heavy top edge bundle is 2-1-1 happy.This is Lemma 5.22 for xe ≥1/2 + ǫ1/2 and ǫ1/2 ≤0.001.
- Conditional measure and expectations: Conditioning on the relevant tree events yields expected counts such as Eν[AT] and Eν[BT] in [0.5, 1.5], supporting subsequent probability bounds.The measure ν remains strongly Rayleigh, while conditioning changes bundle marginals by controlled amounts.
- Lemma 5.23: 0.005ǫ2 is the probability guarantee that at least one of two good half top edge bundles is 2-1-1 happy.The argument first establishes a conditional low-count event with probability at least 0.01, then invokes Lemma A.1.
- Lemma 5.24: 0.01 is the final probability lower bound that two suitable bundles are 2-2-2-happy under the stated small-ǫ1/2 conditions.The proof obtains an Ω(1) conditional event probability and then combines the required events quantitatively.