Transcript Approximation Algorithm of Traveling Salesman Problem

Approximation Algorithm of
Traveling Salesman Problem
By Lin, Jr-Shiun & Chio, Jae Sung
Speaker : Lin, Jr-Shiun
What is TSP?


Design the shortest, or minimal cost,
route for a salesman who wants to
travel EVERY cities ONLY ONCE
and ,lastly, backs to home city.
In graph, we need to find a tour that
starts at a node, visits every other node
exactly once, and returns to the starting
node.
What is TSP


Definition: Find a path through a
weighted graph which starts and ends
at the same vertex, includes every other
vertex exactly once, and minimizes the
total cost of edges. (NIST)
TSP is classify as NP-complete problem,
that means no polynomial algorithm can
guarantee to come within countable(?)
times of the shortest tour.
Christofides Algorithm





Nicos Christofides find a way to slove TSP
problem (1976):
1: find a minimum spanning tree T.
2: find a perfect matching M from nodes with
odd degree.
3: combine the edges of M and T to graph G
4: find an Euler cycle in G by skipping vertices
already seen
Christofides Algorithm
Even nodes with odd degree??


How can I know that I always have
even number of nodes, which have odd
degree, for me to do the MATCHING?
From handshaking lemma: in any graph,
the sum of all the vertex-degrees is
equal to twice the number of edges.
Even nodes with odd degree??



let S (d) = 2m, where m= number of edges.
Therefore S(d) is even.
Let Se(d) to be the sum of degrees of the
vertices which have even degree, Se(d) is
also even.
Therefore S(d)-Se(d) = 2k, k=1,2,…, which
means that the sum of degrees of the
vertices which have odd degree each is also
an even number. Thus there are even
numbers of vertices which have odd number
of degree. (Dr. Giri Narasimhan)
Metric TSP




To convert general TSP to Metric TSP, we
need to add weight to each edges.
Why Metric?
in metric TSP, it suffices to find a cyclic tour
that visits each vertex at least once, rather
than exactly once. Using the triangle
inequality, we can always shortcut a vertex
that is visited more than once without
increasing the cost of the tour.
Metric TSP can be approximated within a
factor of 3/2.
3/2-approximation



Let c(TSP) be the cost of the minimum TSP
tour, c(MST) be the cost of the MST, and c(M)
be the cost of the matching M.
Clearly, c(MST) <=(1 – 1/n)c(TSP ), because
n - 1 edges of a TSP are a spanning tree of
the graph. Moreover, c(M) <=(TSP)/2
Because of the triangle inequality, the
minimum tour on a elements subset of
vertices has cost at most c(TSP).
3/2-approximation (cont.)

If this subset is even cardinality, then
the positive minimum cost matching on
it has cost at most c(TSP)/2, because
the minimum tour is then a disjoint
union of two matchings. The set of
vertices of odd degree in a spanning
tree is of even cardinality.
3/2-approximation (cont.)


An Euler tour exists on the multiset of
edges of MST and M because each
vertex in the edge induced subgraph
has even degree. The cost of the Euler
tour is at most [c(MST ) + c(M)]
<=(3/2 – 1/n)c(TSP ). (Uriel Feige)
As n goes to infinity, it becomes 3/2
apporximation.