∆∆∆
J. A A
Because the random choices in each iteration of the main loop are independent, we can simplify the algorithm by changing the rounding criterion as follows, where N = 2 lg n:
x0(v) = ®1 with probability 1 (1 x⇤(v))N , 0 otherwise,
Let C be the set of vertices returned by this algorithm. Each edge uv is left uncovered by C with probability (1 x⇤(u))N (1 x⇤(v))N 1/4N = 1/n4. It follows that C is a vertex cover with probability at least 1 1/n2. On the other hanfid, linearity of expectation immediately implies that the expected size of C is exactly N · OPT 2 lg n · OPT.
If we want to guarantee a vertex cover, we can modify the main loop in A L - V C to continue running until every edge is covered. The loop will terminate after O(logn) iterations with high probability, and the expected size of the resulting vertex cover is still at most O(log n) · OPT. Thus, at least in expectation, we obtain the same O(log n) approximation ratio (at least in expectation) as our original greedy algorithm.
This randomized rounding strategy can be generalized to the lightest set cover problem, where each subset in the input family has an associated weight, and the goal is to find the lightest collection of subsets that covers the ground set. The resulting rounding algorithm computes a set cover whose expected weight is at most O(log |F|) times the weight of the lightest set cover, matching the performance of the greedy algorithm for unweighted set cover. The dual of this algorithm is a randomized O(log |X|)- approximation algorithm for weighted hitting set (where every item in the ground set has a weight).
Derandomization: Greedy set cover with prices with proof via LP duality
J.8 Traveling Salesman: The Bad News
The traveling salesman problem problem asks for the shortest Hamiltonian cycle in a
weighted undirected graph. To keep the problem simple, we can assume without loss of
generality that the underlying graph is always the complete graph K for some integer n; n n
thus, the input to the traveling salesman problem is just a list of the 2 edge lengths. Not surprisingly, given its similarity to the Hamiltonian cycle problem, it’s quite easy to prove that the traveling salesman problem is NP-hard. Let G be an arbitrary undirected graph with n vertices. We can construct a length function for Kn as follows:
`(e)=®1 ifeisanedgeinG, 2 otherwise.
This is sometimes bowdlerized into the traveling salesperson problem. That’s just silly. Who ever heard of a traveling salesperson sleeping with the farmer’s child?
J.. Traveling Salesman: The Good News
Now it should be obvious that if G has a Hamiltonian cycle, then there is a Hamiltonian cycle in Kn whose length is exactly n; otherwise every Hamiltonian cycle in Kn has length at least n + 1. We can clearly compute the lengths in polynomial time, so we have a polynomial time reduction from Hamiltonian cycle to traveling salesman. Thus, the traveling salesman problem is NP-hard, even if all the edge lengths are 1 and 2.
There’s nothing special about the values 1 and 2 in this reduction; we can replace them with any values we like. By choosing values that are su ciently far apart, we can show that even approximating the shortest traveling salesman tour is NP-hard. For example, suppose we set the length of the ‘absent’ edges to n + 1 instead of 2. Then the shortest traveling salesman tour in the resulting weighted graph either has length exactly n (if G has a Hamiltonian cycle) or has length at least 2n (if G does not have a Hamiltonian cycle). Thus, if we could approximate the shortest traveling salesman tour within a factor of 2 in polynomial time, we would have a polynomial-time algorithm for the Hamiltonian cycle problem.
Pushing this idea to its limits us the following negative result.
Theorem J.. For any function f (n) that can be computed in time polynomial in n, there is no polynomial-time f (n)-approximation algorithm for the traveling salesman problem on general weighted graphs, unless P=NP.
J. Traveling Salesman: The Good News
Even though the general traveling salesman problem can’t be approximated, a common special case can be approximated fairly easily. The special case requires the edge lengths to satisfy the so-called triangle inequality:
`(u, w) `(u, v) + `(v, w) for any vertices u, v, w.
This inequality is satisfied for geometric graphs, where the vertices are points in the plane (or some higher-dimensional space), edges are straight line segments, and lengths are measured in the usual Euclidean metric. Notice that the length functions we used above to show that the general TSP is hard to approximate do not (always) satisfy the triangle inequality.
With the triangle inequality in place, we can quickly compute a -approximation for the traveling salesman tour as follows. First, we compute the minimum spanning tree T of the weighted input graph; this can be done in O(n2 log n) time (where n is the number of vertices of the graph) using any of several classical algorithms. Second, we perform a depth-first traversal of T, numbering the vertices in the order that we first encounter them. Because T is a spanning tree, every vertex is numbered. Finally, we return the cycle obtained by visiting the vertices according to this numbering.
TheoremJ.. Adepth-firstorderingoftheminimumspanningtreegivesa -approximation of the shortest traveling salesman tour.
J. A A
66
7575
11
2423
34
A minimum spanning tree T , a depth-rst traversal of T , and the resulting approximate traveling salesman tour.
Proof: Let OPT denote the cost of the optimal TSP tour, let MST denote the total length of the minimum spanning tree, and let A be the length of the tour computed by our approximation algorithm. Consider the ‘tour’ obtained by walking through the minimum spanning tree in depth-first order. Since this tour traverses every edge in the tree exactly twice, its length is 2 · MST. The final tour can be obtained from this one by removing duplicate vertices, moving directly from each node to the next unvisited node.; the triangle inequality implies that taking these shortcuts cannot make the tour longer. Thus, A 2 · MST. On the other hand, if we remove any edge from the optimal tour, we obtain a spanning tree (in fact a spanning path) of the graph; thus, MST OPT. We conclude that A 2 · OPT; our algorithm computes a -approximation of the optimal tour. É
We can improve this approximation factor using the following algorithm discovered by Nicos Christofides in . As in the previous algorithm, we start by constructing the minimum spanning tree T . Then let O be the set of vertices with odd degree in T ; it is an easy exercise (hint, hint) to show that the number of vertices in O is even.
In the next stage of the algorithm, we compute a minimum-cost perfect matching M of these odd-degree vertices. A perfect matching is a collection of edges, where each edge has both endpoints in O and each vertex in O is adjacent to exactly one edge; we want the perfect matching of minimum total length. A minimum-cost perfect matching can be computed in polynomial time using maximum-flow techniques, which are described in a di erent lecture note.
Now consider the multigraph T [ M; any edge in both T and M appears twice in this multigraph. This graph is connected, and every vertex has even degree. Thus, it contains an Eulerian circuit: a closed walk that uses every edge exactly once. We can compute such a walk in O(n) time with a simple modification of depth-first search. To obtain the final approximate TSP tour, we number the vertices in the order they first appear in some Eulerian circuit of T [ M, and return the cycle obtained by visiting the vertices according to that numbering.
TheoremJ.. Givenaweightedgraphthatobeysthetriangleinequality,theChristofides heuristic computes a ( / )-approximation of the shortest traveling salesman tour.
J.. k-center Clustering
77 6565 11 2424 33
A minimum spanning tree T , a minimum-cost perfect matching M of the odd vertices in T , an Eulerian circuit of T [ M , and the resulting approximate traveling salesman tour.
Proof: LetAdenotethelengthofthetourcomputedbytheChristofidesheuristic;letOPT denote the length of the optimal tour; let MST denote the total length of the minimum spanning tree; let MOM denote the total length of the minimum odd-vertex matching.
The graph T [M, and therefore any Euler tour of T [M, has total length MST+MOM. By the triangle inequality, taking a shortcut past a previously visited vertex can only shorten the tour. Thus, A MST + MOM.
By the triangle inequality, the optimal tour of the odd-degree vertices of T cannot be longer than OPT. Any cycle passing through of the odd vertices can be partitioned into two perfect matchings, by alternately coloring the edges of the cycle red and green. One of these two matchings has length at most OPT/2. On the other hand, both matchings have length at least MOM. Thus, MOM OPT/2.
Finally, recall our earlier observation that MST OPT.
Putting these three inequalities together, we conclude that A 3 · OPT/2, as claimed. É
Four decades after its discovery, Christofedes’ algorithm is the best approximation algorithm known for metric TSP, although better approximation algorithms are known for interesting special cases. In particular, there have been several recent breakthroughs for the special case where the underlying metric is determined by shortest-path distances in an unweighted graph G; this special case is often called the graphic traveling salesman problem. The best approximation ratio known for this special case is 7/5, from a algorithm of Seb and Vygen.
J. k-center Clustering
The k-center clustering problem is defined as follows. We are given a set P = {p1, p2, . . . , pn} of n points in the plane and an integer k. Our goal to find a collection of k circles that collectively enclose all the input points, such that the radius of the largest circle is as
The k-center problem can be defined over any metric space, and the approximation analysis in this section holds in any metric space as well. The analysis in the next section, however, does require that the points come from the Euclidean plane.