§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.
§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
No comments:
Post a Comment