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.
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.
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.
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
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.
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.
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 = ∞.
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
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