Approximation Algorithm

Instead of seeking an exact solution for NP problems, we could seek an approximate solution to optimization problems, e.g. for the traveling salesman or knapsack problems.

 

Accuracy Ratio Definition

Let f(sa) be the value of the objective function, f, of the approximation algorithm and f(s*) is the value of the exact solution then the accuracy ratio is

 

r(sa) = f(sa)/f(s*) for minimizing the objective function

or = f(s*)/f(sa) maximizing the objective funciton

 

 

The approximation called is called c approximate if

 

r(sa) ≤ c

 

The smallest c that holds for all instances of the problem is called the performance ratio.

 

Approximation Algorithms for Traveling Salesman

Before we present some polynomial approximate algorithms, consider weather or not it is possible to construct a finite c-approximate algorithm for the traveling salesman problem. The answer is no, unless P = NP.

Theorem

If exist a polynomial time c-approximation algorithm for the traveling salesman problem then P = NP

 

Proof

We prove by construction, specifically we use the polynomial time c-approximation algorithm  for the traveling salesman problem to construct a polynomial time algorithm for Hamilton circuit problem.

 

Suppose exists such an algorithm A with constant c then an approximate solution, sa, will have f(sa) ≤ cf(s*), where s* is the optimal solution.

 

We use algorithm to construct the algorithm to solve the Hamiltonian circuit in polynomial time for any graph.

 

Let G be an arbitrary graph with n vertices. We map G to a complete weighted graph G' by assigning weight 1 to each edge in G and weight cn+1 to edges not in G.

 

1. If G has a Hamiltonian circuit, its length in G' is n.

It is an optimal solution to the traveling salesman problem for G'.

If sa is an approximate solution obtained for G' using algorithm A then f(sa) ≤ cn by assumption (using f(sa) ≤ cf(s*)).

Meaning, if G has a Hamiltonian circuit then f(sa) ≤ cn. (*)

 

2. If G does not have a Hamiltonian circuit then the shortest tour in G' must contain at least one edge cn+1 and f(sa) ≥ f(s*) > cn.

Meaning, if G does not have a Hamiltonian circuit then f(sa) > cn. (**)

 

So if  the approximation algorithm for the traveling salesman problem runs in polynomial time we can solve the Hamiltonian circuit decision problem in polynomial time by using inequalities (*) and (**).

 

QED

 

We suspect that P ≠ NP, so we suspect there does not exist a polynomial time approximate algorithm with finite c for the traveling salesman problem.

 

This does not mean that graphs with restrictions cannot have c-approximations.

Nearest-neighbor Approximation for the Traveling Salesman in a Complete Graph

Note there is a mistake in the book, it does not state that the graph should be complete.

 

Step 1: choose an arbitrary city as the start

 

Step 2: Repeat until all the cities have been visited, go to the nearest unvisited city

 

Step 3: Return to the starting city

 

Note that the graph must be complete to insure that the start city is adjacent to the last city.

 

Illustrate the algorithm on a graph of a box with an X inside. Make the return edge large.

calculate r(sa) = f(s*)/f(sa)

Show that by changing the weighting of the return edge, to w get r(sa) ~ w

 

So, RA = ∞ for the nearest neighbor approximation.

 

Euclidean Weighted Graph

A Euclidean weighted graph wave weights, d[i, j] with the properties

 

Triangle inequality: d[i, j] ≤ d[i, k] + d[k, j]

Symmetry: d[i, j] = d[j, i]

 

The nearest neighbor approximation for the traveling salesman problem in a complete Euclidean graph has accuracy ratio

 

f(sa)/f(s*) ≤ (1/2)(lg n + 1) 

(given without proof).

 

Still RA = ∞.

 

Twice-around the Minimum Spanning Tree

 

Step 1: Construct a minimum spanning tree of the graph

 

Step 2: Starting at an arbitrary vertex, walk around the minimum spanning tree recording all the vertices. (This can be done by a tree traversal and recording using preorder and postorder visits.)

 

Step 3: Scan the vertex list obtained in step 2 and eliminate from it all repeated occurrences of the same vertex except the starting and ending vertex. (This step is equivalent to making short cuts.) The remaining vertices on the list represent the approximate tour.

 

Again the tree must be complete, for there to exist short cuts.

 

Illustrate

 

Theorem

The twice around the minimum spanning tree is a 2-approximation algorithm for the traveling salesman with Euclidean distances.

 

Proof

We need to show that f(sa) ≤ 2f(s*)

 

Removing any edge from s* yields a spanning tree T with weight w(T).

T is not necessarily a minimum spanning tree (MST) so its weight must be greater than or equal to the weight of a minimum spanning tree, w(MST). Also because removing an edge from s* reduces f(s*):

 

f(s*) > w(T) ≥ w(MST)

or

2 f(s*) > 2w(MST) ( = length of the walk obtained in step 2) (*)

(above always true)

 

The possible shortcuts outlined in step 3 cannot increase the length of the tour in a graph with Euclidian distances, so using the definition of the objective function

 

the length of the walk obtained in step 2 (= 2w(MST) ) ≥ the length of the tour (= f(sa))

2w(MST ) ≥ f(sa) (**)

(above true only for graphs with Euclidian distances)

 

Combining (*) and (**)

 

2 f(s*) > f(sa)

 

QED