Scribd
Upload
86 views13 pages

The Traveling Salesman Problem Approximation

This document discusses approximation algorithms for the Traveling Salesman Problem (TSP). It presents a 2-approximation algorithm that finds the minimum spanning tree (MST) of the graph and doubles its edges to create an Eulerian graph. It then finds an Eulerian circuit to produce a tour. The document also describes a 1.5-approximation algorithm that finds the MST, computes a minimum weight matching on odd-degree vertices, and combines them into a tour.

Uploaded by

soniyee
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
86 views13 pages

The Traveling Salesman Problem Approximation

This document discusses approximation algorithms for the Traveling Salesman Problem (TSP). It presents a 2-approximation algorithm that finds the minimum spanning tree (MST) of the graph and doubles its edges to create an Eulerian graph. It then finds an Eulerian circuit to produce a tour. The document also describes a 1.5-approximation algorithm that finds the MST, computes a minimum weight matching on odd-degree vertices, and combines them into a tour.

Uploaded by

soniyee
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 13

The Traveling Salesman Problem

Approximation
Traveling Salesman Problem
• Traveling Salesman Problem (TSP): Given a
complete graph with nonnegative edge costs,
Find a minimum cost cycle visiting every vertex
exactly once.

• Application (Example): Given a number of cities


and the costs of traveling from any city to any
other city, what is the cheapest round-trip route
that visits each city exactly once and then
returns to the starting city
Triangle Inequality
a

a+b≥c b

• For example, cost of an edge as the euclidian distance


between two points.

• Metric Traveling Salesman Problem (metric TSP): Given


a complete graph with edge costs satisfying triangle
inequalities, Find a minimum cost cycle visiting every
vertex exactly once.
Metric TSP approximation
• The cost function satisfies the triangle inequality
for all vertices u, v, w in V
– c(u,w) <= c(u,v) + c(v,w)

• Eulerian graphs and Eulerian circuits:


– Eulerian circuit: cycle that uses each edge exactly
once
– Eulerian graph: graph with a Eulerian circuit
– An undirected graph is Eulerian iff each vertex has
even degree
Approximate-TSP-tour (G)
1. Find MST T of G
2. Double every edge of the MST to get a
Eulerian graph G’
Idea: Get a tour from Minimum spanning
tree without increasing its cost too much
(at most twice).
3. Find an Eulerian circuit E on G’
4. Output the vertices of G in order of
appearance in E
First let’s compare the optimal solutions of MST
and TSP for any problem instance G=(V,E)

Optimal TSP sol-n A tree obtained from the tour Optimal MST sol-n

(*)
Cost (Opt. TSP sol-n) ≥ Cost (of this tree) ≥ Cost (Opt. MST sol-n)
What is the cost of the tour
compared to the cost of MST?
5

6
3
1 4
2

Triangle inequality
cost   c(e)
dashed arcs e
 2   c(e)
arcs e
TSP - e  MST
 2  cost(MST)  2  cost(optimal TSP)
Analysis
• This is a 2 approximation algorithm
• MST < Euler Cycle = 2 * MST <= 2.0 TSP

• Can we improve this?


– The previous algorithm was a factor 2 algorithm.
• Recall Step 2:
Double every edge of the MST to get a Eulerian graph G’
– If we can work avoid this, we could possibly have a
better solution !
Perfect Matching
• Matching: a matching is a subset M
of E such that for all vertices v in V,
at most one edge is incident on v.

• Perfect Matching: is a matching M


such that for all vertices v in V
exactly one edge of M is incident on
v.
Minimum Weight Matching
• Perfect matching with minimum sum of
weights

• Input: Complete weighted graph s, |v| is


even
• Output: A pair of values (vi, vj) such that
the sum of weights is smallest.
1.5 approximation algorithm
(Known as Christofides Heuristics)
1. Find a MST T of G
2. Find a minimum weight (perfect) matching
M on the set of odd degree vertices in T.
3. Add M to T to get the Eulerian graph G’
4. Find an Eulerian circuit E on G’ by skipping
vertices already seen (shortcutting)
5. Output the vertices of G in order of appearance
in E
Step 2:
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?

• Let Sum(d) = 2m, where m= number of edges. Therefore


Sum(d) is even.
• Let SumEven(d) to be the sum of degrees of the vertices
which have even degree, SumEven(d) is also even.
• Therefore SumOdd(d)=Sum(d)-SumEven(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.
Analysis
TSP = match1 + match2 (we can divide TSP in two mutually
exclusive matchings)
MWM <= min{ match1, match2}

 Match1 + match 2 = TSP


 MWM + MWM <= TSP (MWM <= match1 and MWM <=
match2)
 MWM <= .5 TSP

MWM <= .5 TSP

MST < Euler Cycle


= MST + MWM <= TSP + .5 TSP
= 1.5 TSP

You might also like