Approximation Algorithm - Part 3 ( Traveling-Salesman Problem)

 

§Problem: A salesman must visits  n cities. Visiting each city exactly once and finishing at the city he starts from (Hamiltonian cycle). There is a non-negative cost c (i, j) to travel from the city i to city j.

§Definition: Given a complete undirected graph G=(V, E) that has nonnegative integer cost  c(u, v) associated with each edge (u, v) in E, the problem is to find a hamiltonian cycle (tour) of G with minimum cost.

§Goal: Find a tour of minimum cost. We assume that every two cities are connected

§NP-Hard problem.

Triangle inequality

•There are approximate algorithms to solve the problem though.

•The approximate algorithms work only if the problem instance satisfies Triangle-Inequality.

•The cost function satisfies the triangle inequality for all vertices u, v, w in V

c(u,w) <= c(u,v) + c(v,w)

•Essentially this means that it is no more costly to go directly from u to v than it would be to go between them via a third point w.

Approximate Algorithm TSP

Approx-TSP (G= (V, E))   

{  

  1. Compute a MST T of G;  

  2. Select any vertex r is the root of the tree;  

  3. Let L be the list of vertices visited in a preorder tree walk of T;  

  4. Return the Hamiltonian cycle H that visits the vertices in the order L;  

}  

Runtime is dominated by MST-PRIM, which is Θ(V2 ).

Approximation Algorithm:  Returns a tour whose cost is never more than twice the cost of an optimal tour (2-approximation algorithm). 

TSP with Triangle Inequality

Step-1

Proof of the Approximation Ratio

§Theorem: APPROX-TSP is a polynomial-time 2-approximation for the traveling-salesman problem with the triangle inequality.

§Consider the optimal tour H∗ and remove an arbitrary edge

§⇒ yields a spanning tree T , So,   c(T) ≤ c(H∗)

Let W be the full walk of the minimum spanning tree Tmin (including repeated visits)

 

A full walk is lists all vertices when they are first visited in preorder, it also lists vertices when they are returned after a sub-tree is visited in preorder. 

Full walk traverses every edge exactly twice, so,  c(W) = 2c(Tmin)

Full walk traverses every edge exactly twice, so     c(W) = 2c(Tmin) ≤ 2c(T) ≤ 2c(H ∗ )

Full walk traverses every edge exactly twice, so             c(W) = 2c(Tmin) ≤ 2c(T) ≤ 2c(H ∗ )

Deleting duplicate vertices from W yields a tour H.

•Deleting duplicate vertices from W yields a tour H with a smaller cost: c(H) ≤ c(W)

                                                        TSP without Triangle Inequality

§If P ≠ NP, then for any constant ρ≥1, there is no polynomial-time approximation algorithm with approximation ratio ρ for the general traveling-salesman problem.

§Suppose to the contrary that there exists a polynomial-time algorithm A for p≥1.
§Now, use algorithm A to solve instance of HAM-CYCLE problem in polynomial-time. Since HAM-CYCLE problem is NP-complete then by theorem:

§If any NP-complete problem is polynomial-time solvable, then P=NP. Equivalently, if any problem in NP is not polynomial-time solvable than no NP-complete problem is polynomial solvable.

§Solving HAM-CYCLE in polynomial-time implies that P=NP.

§Since the HAM-CYCLE is NP-complete and we assumed and we assumed that P≠NP, a contradiction arises.

§Reduction

§Let G = (V, E) be an instance of the Hamiltonian cycle problem. We want to determine efficiently whether G contains a Hamiltonian cycle by making use of an algorithm A. We transform G into an instance of the TSP problem as follows:

§Consider a complete graph G`=(V, E`) where E` = {(u, v): u, v in V and u≠v}. Assign an integer cost to each edge in E` as follows:

c(u,v) =  1                if (u, v) in E

P|V| + 1                   otherwise

Because algorithm A is guaranteed to return a tour of cost no more than P times the cost of an optimal tour, if graph G contains a Hamiltonian cycle, then A must return it. If G has no Hamiltonian cycle, then A returns a tour of cost more than P|V|. Therefore, we can use algorithm A to solve the Hamiltonian cycle problem in polynomial time and this is impossible unless P=NP