1 of 31

Approximation Algorithms for TSP

Tsvi Kopelowitz

Ariel Rosenfeld

1

2 of 31

HC-Hamiltonian Cycle

Input: graph G=(V,E)
Output: a cycle tour in G that visits each vertex exactly once.

Problem is known to be NP-Hard.

2

3 of 31

TSP – Traveling Salesman Problem

Input: a complete graph G=(V,E) with edges of non-negative cost (c(e)).
Output: find a cycle tour of minimum cost that visits each vertex exactly once.
The problem is NP-Hard (reduction from HC) .

… and hard to approximate.

3

4 of 31

Hardness of Approximation

Claim: For every c>1, there is no polynomial time algorithm which can approximate TSP within a factor of c, unless P=NP.

4

5 of 31

Proof

By reduction from Hamiltonian cycle.

Given a graph G, we want to determine if it has a HC.
Construct a complete graph G’ with same vertices as G, where each edge e has weight 1 if it is in G, and weight c*n if it is not (n is the number of vertices).

5

6 of 31

Example

6

G=

7 of 31

Example

1

c*n

7

G’=

8 of 31

Proof

Run algorithm A for solving TSP within a factor of c.

�

If there is a HC, TSP has a solution of weight n, and approximation is at most c*n
If there is no HC, then every tour in TSP has at least one edge of weight c*n, so weight of tour is at least c*n +n-1.

8

9 of 31

Metric

A (complete) graph with weight function w on the edges is called a metric if:

For any two vertices u,v in the graph:� w(u,v)=w(v,u)
The Triangle Equality holds in the graph.

9

10 of 31

Triangle Inequality

Recall: The triangle inequality holds in a (complete) graph with weight function w on the edges if for any three vertices u,v,x in the graph:��
Metric TSP is still NP-hard, but now we can approximate.

10

11 of 31

2-approximation

Given G, construct an MST T for G

(since it is a metric graph, it doesn’t matter whether it is directed or not).

For each edge in T create a double edge. (This will guarantee that the degrees of all the vertices are even)
Find an Euler tour in the doubled T.

11

12 of 31

12

13 of 31

2-approximation

Given G, construct an MST T for G

(since it is a metric graph, it doesn’t matter whether it is directed or not).

For each edge in T create a double edge. (This will guarantee that the degrees of all the vertices are even)
Find an Euler tour in the doubled T.
Create shortcuts in the Euler tour, to create a tour.

13

14 of 31

2-approximation

How will we create these “shortcuts”?

Traverse the Euler tour.
Whenever the Euler tour returns to a vertex already visited, “skip” that vertex.

The process creates a Hamiltonian cycle.

14

15 of 31

15

16 of 31

16

17 of 31

2-approximation

Claim: The above algorithm gives a 2-approximation for the TSP problem (in a metric graph with the triangle inequality).

Proof:

Definitions:

OPT is the optimal solution (set of edges) for TSP.
A is the set of edges chosen by the algorithm.
EC is the set of edges in the Euler cycle.

17

18 of 31

2-approximation

Proof Continued:

cost(T) ≤ cost(OPT):

since OPT is a cycle, remove any edge and obtain a spanning tree.

cost(EC) = 2cost(T) ≤ 2cost(OPT).
cost(A) ≤ cost(EC)

A is created by taking “shortcuts” from EC. (These are indeed shortcuts, because of the triangle inequality.)

So cost(A) ≤ 2cost(OPT) . •

18

19 of 31

Example

19

h

c

b

a

d

e

g

f

MST

h

c

b

d

e

g

f

Input�(assume Euclidean distances)

a

20 of 31

20

h

c

b

a

d

e

g

f

Walk W�a b c b h b a d e f e g e d a

h

c

b

a

d

e

g

f

Hamiltonian Cycle H�a b c h d e f g a

2-approx.

21 of 31

1.5 TSP Approximation Algorithm�(Known as Christofides Heuristics)

Professor Nicos Christofides extended the 2.0 TSP and published that the worst-case ratio of the extended algorithm was 3/2.

21

22 of 31

1.5 Approximation

Algorithm:

1. Compute MST graph T.

2. Compute a minimum-weighted matching graph M between all Odd- degree vertices.

3. Combine T and M as edge set and Compute an Euler Cycle.

4. Traverse each vertex taking shortcuts to avoid visited nodes.

22

23 of 31

1.5 Approximation

What is a Minimum-weighted Matching?

It creates a MWM on a set of the nodes having an odd degree.

Why odd degree?

Property of Euler Cycle (if all edges all of even-degree, EC exists)

Why 1.5 TSP?

MST < Euler Cycle <= MWM+MST <= 1.5 TSP

(need to show MWM <= ½ TSP)

23

24 of 31

1.5 approx.

h

c

b

a

d

e

g

f

MST T

h

c

b

e

g

f

Matching M

25 of 31

1.5-approximation

Claim: The above algorithm gives a 1.5-approximation for the TSP problem (in a metric graph with the triangle inequality).

Proof: Denote:

OPT, A, and EC as before.
M is the set of edges in the minimum matching.

25

26 of 31

1.5-approximation

Proof Continued:

cost(M) ≤ cost(OPT)/2

The minimum tour on any subset B of vertices has a cost of at most cost(OPT)�

A Hamiltonian cycle in B can be extracted from OPT by “skipping” vertices not in B, resulting in a tour lighter than OPT, due to the triangle inequality.
If B is of even size then divide the minimum tour on B into two disjoint matchings of B.�
The lighter matching of the two (denote by M’) has weight at most cost(OPT)/2.

26

27 of 31

27

1.5-approximation

9

3

1

4

1

5

M’

28 of 31

1.5-approximation

Proof Continued:�

cost(M) ≤ cost(M’) ≤ cost(OPT)/2.

The number of odd vertices in a graph is even. (Always, but Why?)�
Choose B to be the set of odd vertices in T.�
M’ is not necessarily the minimum matching of B, but cost(M) ≤ cost(M’).

28

29 of 31

1.5-approximation

Proof Continued:

EC is an Euler Cycle in .�
cost(EC) = cost(T)+cost(M) ≤ 1.5cost(OPT).�
cost(A) ≤ cost(EC) ≤ 1.5cost(OPT)�

•�

29

30 of 31

h

c

b

e

g

f

Matching M

h

c

b

e

g

f

Optimal Tour Γ* on Odd Nodes

Separating the optimal tour of B into 2 matchings

31 of 31

Matching

h

c

b

a

d

e

g

f

G' = MST + Matching

h

c

b

e

g

f

Matching M