TSP, set cover & the general techniques

Metric TSP: a 2-approximation from an MST

In the traveling-salesperson problem (TSP) you are given a complete undirected graph with edge costs $c$, and you want a minimum-cost Hamiltonian cycle (a tour visiting every vertex once). General TSP is NP-hard. But when the costs satisfy the triangle inequality $c(u,w)\le c(u,v)+c(v,w)$ — true for any distances in a metric space, e.g. points on a plane — there is a clean 2-approximation:

APPROX-TSP-TOUR(G, c)
  pick a root r
  T = MST-PRIM(G, c, r)          // minimum spanning tree
  H = preorder walk of T from r   // vertices in first-visit order
  return the cycle H

Why it is a 2-approximation. Three inequalities chain together. Let $H^{\ast }$ be an optimal tour and $T$ the MST.

1. $c(T)\le c(H^{\ast })$ — deleting any one edge from the optimal tour leaves a spanning tree, so the minimum spanning tree is no costlier than the tour. The MST is the lower bound.
2. A full walk $W$ of $T$ (down and back up every branch) traverses each tree edge exactly twice: $c(W)=2c(T)$.
3. The preorder walk $H$ is $W$ with repeated vertices skipped. Each skip replaces a path $u\to v\to w$ by the direct edge $u\to w$; by the triangle inequality this never increases cost: $c(H)\le c(W)$.

Chaining: $c(H)\le c(W)=2c(T)\le 2c(H^{\ast })$. $■$

Worked example. Five points: $a(0,0)$, $b(0,4)$, $c(3,4)$, $d(3,0)$, $e(6,2)$ with Euclidean distance. Prim from $a$ builds an MST of cost $\approx 13.21$. Its preorder walk is $a-d-e-c-b$, a tour of cost $\approx 17.21$. The guarantee $17.21\le 2\times 13.21=26.42$ holds comfortably (and $17.21\le 2c(H^{\ast })$ since $c(H^{\ast })\ge c(T)$).

General TSP has no constant-ratio approximation

Drop the triangle inequality and the picture collapses. Theorem 35.3: if $P\ne NP$, then for no constant $\rho \ge 1$ does a polynomial-time $\rho$-approximation for general TSP exist.

Sketch (gap amplification). Reduce HAM-CYCLE: given $G=(V,E)$, build a complete graph $G^{\prime }$ with $c(u,v)=1$ if $(u,v)\in E$, else $c(u,v)=\rho |V|+1$. If $G$ has a Hamiltonian cycle, the optimal $G^{\prime }$ tour costs $|V|$; if not, every tour uses a heavy edge and costs $>\rho |V|$. A $\rho$-approximation would distinguish the two cases, solving HAM-CYCLE in polynomial time — so $P=NP$. The trick is to manufacture a gap of factor $\rho +1$ that any $\rho$-approximation must respect.

Greedy set cover: an $H(n)$-approximation

Set cover: given a universe $X$ of $n$ elements and a family $\mathcal{F}$ of subsets whose union is $X$, find the smallest subfamily covering $X$. GREEDY-SET-COVER repeatedly takes the set covering the most still-uncovered elements.

Theorem 35.4: greedy is an $H(n)=\Theta (\lg n)$-approximation (where $H(n)={\sum }_{i=1}^{n}1/i$). Why: if the optimum uses $k$ sets, then at any moment $k$ sets cover all $|U_i|$ uncovered elements, so by averaging some set covers $\ge |U_i|/k$. Greedy takes at least that many, so $|U_{i+1}|\le |U_i|(1-1/k)\le |X|e^{-i/k}$. This drops below $1$ once $i>k\ln |X|$, giving $|C|\le k\lceil \ln |X|\rceil =|C^{\ast }|\cdot O(\lg n)$. The ratio is logarithmic, not a constant — and that is essentially unavoidable for set cover.

LP rounding: weighted vertex cover, 2-approximation

For weighted vertex cover the matching trick breaks (a heavy vertex may anchor a light edge). Instead, write the integer program — minimize ${\sum }_{v}w(v)x(v)$ subject to $x(u)+x(v)\ge 1$ per edge, $x(v)\in \{0,1\}$ — then relax $x(v)\in [0,1]$ to a linear program (solvable in polynomial time). Solve the LP for fractional $\bar{x}$, then round: put $v$ in the cover iff $\bar{x}(v)\ge \frac{1}{2}$.

This is a 2-approximation (Theorem 35.6). Feasibility: each edge has $\bar{x}(u)+\bar{x}(v)\ge 1$, so at least one endpoint has $\bar{x}\ge \frac{1}{2}$ and is taken. Cost: for every chosen $v$, $1\le 2\bar{x}(v)$, so $w(C)\le {\sum }_{v}w(v)\cdot 2\bar{x}(v)=2z^{\text{LP}}\le 2w(C^{\ast })$ — the LP optimum $z^{\text{LP}}$ is a lower bound on the integer optimum. Rounding $\frac{1}{2}$ up to $1$ is exactly where the factor 2 comes from.

And when $P=NP$ would not even help: the FPTAS for subset sum

Subset sum (NP-complete) admits an FPTAS: keep a list of achievable subset sums, but trim values within a factor $(1+\delta )$ of each other, with $\delta =\epsilon /2n$. Trimming keeps the list polynomial, $O(n^2/\epsilon )$, while the compounded error stays $(1+\delta {)}^n\le e^{\epsilon /2}\le 1+\epsilon$. So you get a $(1+\epsilon )$-approximation in time polynomial in $n$ and $1/\epsilon$ — the best you can hope for short of solving it exactly.