15.083 Lecture 22: Approximation Algorithms II

15.083J Integer Programming and Combinatorial Optimization Fall 2009 Approximation Algorithms II The traveling salesman problem Theorem 1. For any polynomial time computable function α(n), TSP cannot be approximated within a factor of α(n), unless P = NP. Proof: • Suppose there is an approximation algorithm A such that A(I) ≤ α(n) · OPT(I) for all instances I of TSP. • We will show that A can be used to decide whether a graph contains a Hamiltonian cycle (which is NP-hard), implying P = NP. • Let G be an undirected graph. We define a complete graph G� on the same vertices as follows: • Edges that appear in G are assigned a weight of 1. • Edges that do not exist in G get a weight of α(n) · n. • If G has a Hamiltonian cycle, the corresponding tour in G� has a cost of n. • If G has no Hamiltonian cycle, any tour in G has cost at least α(n) · n + 1. • Hence, if we run A on G� it has to return a solution of cost ≤ α(n) · n in the first case, and a solution of cost > α(n) · n in the second case. • Thus, A can be used to decide whether G contains a Hamiltonian cycle. The metric traveling salesman problem A 2-approximation algorithm for ΔTSP: 1. Find a minimum spanning tree T of G. 2. Double every edge of T to obtain a Eulerian graph. 3. Find a Eulerian tour T on this graph. 4. Output the tour that visits the vertices of G in the order of their first appearance in T . Let C be this tour. Proof: 1 • Note that cost(T ) ≤ OPT because deleting an edge from an optimal tour yields a spanning tree. • Moreover, cost(T ) = 2 · cost(T ). • Because of the triangle inequality, cost(C) ≤ cost(T ). • Hence, cost(C) ≤ 2 · OPT. A 3/2-approximation algorithm for ΔTSP: 1. Find a minimum spanning tree T of G. 2. Compute a min-cost perfect matching M on the set of odd-degree vertices of T . 3. Add M to T to obtain a Eulerian graph. 4. Find a Eulerian tour T on this graph. 5. Output the tour that visits the vertices of G in the order of their first appearance in T . Let C be this tour. Proof: • Let τ be an optimal tour, i.e., cost(τ ) = OPT. • Let τ � be the tour on the odd-degree nodes of T , obtained by short-cutting τ . • By triangle inequality, cost(τ � ) ≤ cost(τ ). • Note that τ � is the union of two perfect matchings. • The cheaper of these two matchings has cost at most cost(τ � )/2. • Hence, 1 cost(C) ≤ cost(T ) ≤ cost(T ) + cost(M ) ≤ OPT + OPT. 2 The set cover problem Input: U = {1, . . . , n}, S = {S1 , . . . , Sk } ⊆ 2U , c : S → Z+ . Output: J ⊆ {1, . . . , k} such that  i∈J Si = U and � 2 i∈J c(Si ) is minimal. • Special case: vertex cover problem. A greedy algorithm: 1. C := ∅. 2. WHILE C �= U DO � c(S ) |S \C | � :S∈S . 3. Let S := arg min 4. Let α := 5. Pick S, and for each e ∈ S \ C, set price(e) = α. 6. C := C ∪ S. c(S) |S\C| . 7. Output the picked sets. • Let e1 , . . . , en be the order in which the elements of U are covered by the greedy algorithm. Lemma 2. For each k ∈ {1, . . . , n}, price(ek ) ≤ OPT/(n − k + 1). Proof: • Let i(k) be the iteration in which ek is covered. • Let O ⊆ S be the sets chosen by an optimal solution. • Let Oi(k) ⊆ O be the sets in O not (yet) chosen by the greedy algorithm in iterations 1, . . . , i(k). • Note that {ek , . . . , en } ⊆ S∈Oi(k) S and � c(S) ≤ OPT. S∈Oi(k) • Hence, there exists a set S ∈ Ok of average cost c(S) OPT at most . n−k+1 |S \ C| • Since ek is covered by the set with the smallest average cost, price(ek ) ≤ OPT . n−k+1 Theorem 3. The greedy algorithm is an (ln n + 1)-approximation algorithm. Proof: 3 • Since the cost of each set picked is distributed among the new elements covered, the total n � cost of the set cover returned by the greedy algorithm is equal to price(ek ). k=1 • By the previous lemma, n � � price(ek ) ≤ k=1 1 1 1 + + ··· + 2 n � · OPT = Hn · OPT. An integer programming formulation: � min c(S)xS S∈S s.t. � xS ≥ 1 e∈U xS ∈ {0, 1} S∈S S�e And its linear programming relaxation: � min c(S)xS S∈S � s.t. xS ≥ 1 e∈U xS ≥ 0 S∈S S�e And its dual: max � ye e∈U s.t. � ye ≤ c(S) S∈S ye ≥ 0 e∈U e∈S “Dual Fitting:” Lemma 4. The vector y defined by ye := price(e) is a feasible solution to the dual linear program. Hn Proof: • Consider a set S ∈ S consisting of k elements. • Number the elements in the order in which they are covered by the greedy algorithm, say e1 , . . . , ek . 4 • Consider the iteration in which the algorithm covers ei . • At this point, S contains at least k − i + 1 uncovered elements. • S itself can cover ei at an average cost of at most • Hence, price(ei ) ≤ • Overall, k � i=1 c(S) . k−i+1 c(S) 1 c(S) and yei ≤ · . k−i+1 Hn k − i + 1 c(S) yei ≤ · Hn � 1 1 1 + + ··· + k k−1 1 � = Hk · c(S). Hn Theorem 5. The greedy algorithm is an Hn -approximation algorithm. Proof: � price(e) = Hn · e∈U � ye ≤ Hn · LP ≤ Hn · OPT. e∈U “LP rounding:” 1. Find an optimal solution to the LP relaxation. 2. Pick all sets S for which xS ≥ 1/f in this solution. Here, f is the frequency of the most frequent element. Theorem 6. The LP rounding algorithm achieves an approximation factor of f . Proof: • Let C be the collection of picked sets. • Consider an arbitrary element e ∈ U . • Since e is in at most f sets, one of them must be picked to the extent of at least 1/f in the fractional cover. • So C is a feasible set cover. • The rounding process increases xS , for each S ∈ C, by a factor of at most f . A tight example: • Consider a hypergraph: vertices correspond to sets, and hyperedges correspond to elements. 5 • Let V = V1 ∪˙ . . . ∪˙ Vk , where each Vi has cardinality k. • There are nk hyperedges: each picks one element from each Vi . • Each set (i.e., vertex) has cost 1. • Picking each set to the extent of 1/k gives an optimal fractional cover of cost n. • Given this fractional solution, the rounding algorithm will pick all nk sets. • On the other hand, picking all sets (vertices) in V1 gives a set cover of cost n. “The primal-dual method:” • Start with a primal infeasible and a dual feasible solution (usually x = 0 and y = 0). • Iteratively improve the feasibility of the primal solution and the optimality of the dual solu­ tion. • The primal solution is always extended integrally. • The current primal solution is used to determine the improvement to the dual, and vice versa. • The cost of the dual solution is used as a lower bound. (Relaxed) complementary slackness: • Primal condition: � – xS �= 0 =⇒ ye = c(S). e∈S • Dual condition: – ye �= 0 =⇒ � xS ≤ f. S�e – Trivially satisfied! A factor f approximation algorithm: 1. x := 0, y := 0. 2. REPEAT 3. Pick an uncovered element e and raise ye until some set 4. Include all tight sets in the cover and update x. 5. UNTIL all elements are covered 6 becomes tight. 6. RETURN x. Proof: � S∈C c(S)xS = ��� S∈C e∈S � � � � ye xS ≤ ye xS ≤ f · ye ≤ f · OPT e∈U 7 S�e e∈U