approx

ptas wiki

example

find mst

double mst to get a Ham'n tour

shortcut tour (skip over any repeated nodes) to obtain shortcut Ham'n cycle

by triangle ineq, cost of shortcut cycle less/eq to cost of tour

cost of one mst less/eq cost of any Ham'n cycle

so cost of shortcut cycle at most twice cost of any Ham'n cycle

so polytime 2-approx

Christofides-Sedyukov

input: complete weighted graph G satisfying triangle inequality

find mst T of G

let H be subgraph of G induced by vertices with odd degree in T

notice: H has even number of nodes   (why ?)

find min-weight perfect matching M of H

let R be edges(T) union edges(M)

notice: R is Eulerian tour of G

shortcut R to form Hamiltonian cycle

polytime (why?)

wt(R) at most 1.5 times min wt Hamiltonian cycle of G

correctness

Sanjeev Arora

proof: for some r ≥ 1, assume r-approx for u-tsp

for Ham'n cycle, consider any instance G=(V,E) with |V|=n

transform G to instance G’ of u-tsp:

• if e in E, set cost(e) to 1

• if e not in E, set cost(e) to qn+1, where q = floor(r)

if G Ham'n, G' has a tsp with cost n

if G not Ham'n, every tsp of G' has cost at least qn+1 + (n-1) = (1+q)n

assume there is an r-approx for u-tsp: it finds a tsp within factor of r of optimal

if G is Hamiltonian this approx finds a tsp with cost at most rn

if G is not Ham'n this approx finds a tsp with cost at least (1+floor(r))n > rn

so we can use this approx to polytime solve Ham'n cycle