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^*$ be an optimal tour and $T$ the MST.

1. $c(T) \le c(H^*)$ — 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) = 2\,c(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) = 2\,c(T) \le 2\,c(H^*)$. $\quad\blacksquare$

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 2\,c(H^*)$ since $c(H^*) \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'$ 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'$ 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^*|\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 \tfrac12$.

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 \tfrac12$ 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 2\,w(C^*)$ — the LP optimum $z^{\text{LP}}$ is a lower bound on the integer optimum. Rounding $\tfrac12$ 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=\varepsilon/2n$. Trimming keeps the list polynomial, $O(n^2/\varepsilon)$, while the compounded error stays $(1+\delta)^n \le e^{\varepsilon/2} \le 1+\varepsilon$. So you get a $(1+\varepsilon)$-approximation in time polynomial in $n$ *and* $1/\varepsilon$ — the best you can hope for short of solving it exactly.