Approximation Algorithms: Combinatorial Approaches Lecture 16: March 7
Approximation Algorithms: Combinatorial Approaches Lecture 16: March 7
The Hamiltonian Path Problem Hamiltonian Path Problem:
Given an undirected graph, find a cycle visiting every vertex exactly once. The Hamiltonian Path problem is NP-complete. Eulerian Path Problem:
Given an undirected graph, find a walk visiting every edge exactly once.
Notice that in a walk some vertices may have been visited more than once. The Eulerian Path problem is polynomial time solvable.
A graph has an Eulerian path if and only if every vertex has an even degree.
The Hamiltonian Path Problem Application: Seating assignment problem:
Given n persons and a big round table of n seats, each pair of persons may like each other or hate each other. Can we find a seating assignment so that everyone likes his/her neighbors (only two neighbors)? Construct a graph as follows. For each person, create a vertex. For each pair of vertices, add an edge if and only if they like each other. Then the problem of finding a seating assignment is reduced to the Hamiltonian path problem.
The Traveling Salesman Problem Traveling Salesman Problem (TSP):
Given a complete graph with nonnegative edge costs,
Find a minimum cost cycle visiting every vertex exactly once. Given a number of cities and the costs of traveling from any city to any other city, what is the cheapest round-trip route that visits each city exactly once and then returns to the starting city? One of the most well-studied problem in combinatorial optimization.
NP-completeness of Traveling Salesman Problem Hamiltonian Path Problem:
Given an undirected graph, find a cycle visiting every vertex exactly once. For each edge, we add an edge of cost 1.
For each non-edge, we add an edge of cost 2. Traveling Salesman Problem (TSP):
Given a complete graph with nonnegative edge costs,
Find a minimum cost cycle visiting every vertex exactly once. The Hamiltonian path problem is a special case of the Traveling Salesman Problem. If there is a Hamiltonian path, then there is a cycle of cost n.
If there is no Hamiltonian path, then every cycle has cost at least n+1.
Inapproximability of Traveling Salesman Problem Theorem: There is no constant factor approximation algorithm for TSP,
unless P=NP. Idea: Use the Hamiltonian path problem. For each edge, we add an edge of cost 1.
For each non-edge, we add an edge of cost 2 nk. If there is a Hamiltonian path, then there is a cycle of cost n.
If there is no Hamiltonian path, then every cycle has cost greater than nk. So, if you have a k-approximation algorithm for TSP,
one just needs to check if the returned solution is at most nk.
If yes, then the original graph has a Hamiltonian path.
Otherwise, the original graph has no Hamiltonian path.
Inapproximability of Traveling Salesman Problem Theorem: There is no constant factor approximation algorithm for TSP,
unless P=NP. If there is a Hamiltonian path, then there is a cycle of cost n.
If there is no Hamiltonian path, then every cycle has cost greater than nk. The strategy is usually like this.
This creates a gap between yes and no instances.
The bigger the gap, the problem is harder to approximate. This type of theorem is called “hardness result” in the literature.
Just like their names, usually they are very hard to obtain.
Approximation Algorithm for TSP There is no constant factor approximation algorithm for TSP,
what can we do then? Observation: in real world situation, the costs satisfy triangle inequality. a c b a + b ≥ c For example, think of cost of an edge
as the distance between two points.
Approximation Algorithm for Metric TSP Metric Traveling Salesman Problem (metric TSP):
Given a complete graph with edge costs satisfying triangle inequalities,
Find a minimum cost cycle visiting every vertex exactly once. First check the bad example. 1 nk 1 This violates triangle inequality! How could triangle inequalities help in finding approximation algorithm?
Lower Bounds for TSP What can be a good lower bound to the cost of TSP? A tour contains a matching. Let OPT be the cost of an optimal tour, since a tour contains two matchings,
the cost of a minimum weight perfect matching is at most OPT/2. A tour contains a spanning tree. So, the cost of a minimum spanning tree is at most OPT.
Spanning Tree and TSP So the thick edges form a minimum spanning tree. Let the thick edges have cost 1,
And all other edges have cost greater than 1. But it doesn’t look like a Hamiltonian cycle at all! Consider a Hamiltonian cycle.
The costs of the edges which are not in the
minimum spanning tree might have very high costs. Not really! Each such edge has cost at most 2
because of the triangle inequality. Edge cost at most 2
Spanning Tree and TSP a b c d e Strategy: Construct the TSP tour from a minimum spanning tree. Use the edges in the minimum spanning tree as many as possible. The center vertex already has degree 2, skip to the next vertex. Cost = e + a + a + b + b + c + c + d + d + e = 2a + 2b + 2c + 2d + 2e = 2(a +b + c + d + e) Cost of a minimum spanning tree MST ≤ OPT SOL ≤ 2MST + SOL ≤ 2OPT
Spanning Tree and TSP How to formalize the idea of “following” a minimum spanning tree?
Spanning Tree and TSP How to formalize the idea of “following” a minimum spanning tree? Key idea: double all the edges and find an Eulerian tour. This graph has cost 2MST.
Spanning Tree and TSP How to formalize the idea of “following” a minimum spanning tree? Key idea: double all the edges and find an Eulerian tour. This graph has cost 2MST.
Strategy: shortcut this Eulerian tour. Spanning Tree and TSP
By triangle inequalites, the shortcut tour is not longer than the Eulerian tour. Spanning Tree and TSP Each directed edge is used exactly once in the shortcut tour.
A 2-Approximation Algorithm for Metric TSP (Metric TSP – Factor 2)
Find an MST, T, of G.
Double every edge of the MST to obtain an Eulerian graph.
Find an Eulerian tour, T*, on this graph.
Output the tour that visits vertices of G in the order of
their first appearance in T*. Let C be this tour.
(That is, shortcut T*) Analysis: cost(T) ≤ OPT (because MST is a lower bound of TSP)
cost(T*) = 2cost(T) (because every edge appears twice)
cost(C) ≤ cost(T*) (because of triangle inequalities, shortcutting)
So, cost(C) ≤ 2OPT
Better approximation? There is a 1.5 approximation algorithm for metric TSP. Hint: use a minimum spanning tree and a maximum matching
(instead of double a minimum spanning tree). Major open problem: Improve this to 4/3? Just for fun: can we design an approximation algorithm for the seating assignment problem? An aside: hardness result is not an excuse to stop working,
but to guide us to identify interesting cases.
Minimum Steiner Tree The Minimum Steiner Tree Problem:
Given an undirected graph G with nonnegative edge costs and whose vertices are partitioned into two sets, required vertices and Steiner vertices, find a minimum cost tree in G that contain all the required vertices and any subset of the Steiner vertices.
Comments