APPROXIMATION ALGORITHMS VERTEX COVER MAX CUT PROBLEMS SELIM KALAYCI FIU-SCS 04/13/2005 Motivation Some optimization problems are NP-hard (by hardness of related decision problem), there is no poly-time algorithm unless P = NP. largest clique smallest vertex cover largest maximum cut ... But: sometimes sub-optimal solutions are kind of OK pretty large clique pretty small vertex cover
pretty large maximum cut ... if algorithms run in poly time (preferably small exponents). APPROXIMATION ALGORITHMS Definition:Approximation algorithm An approximation algorithm for a problem is a polynomial-time algorithm that, when given input I, outputs an element of FS(I). Feasible solution set A feasible solution is an object of the right type but not necessarily an optimal one. FS(I) is the set of feasible solutions for I.
APPROXIMATION RATIO Approximation algorithm has approximation ratio of (n), if for any input of size n, the outcome O of its solution is within factor (n) of outcome of optimal solution O*, i.e. 1 Max (O/O*, O*/O) (n) Minimization Maximization problem problem APPROXIMATION RATIO An algorithm with guaranteed approximation ratio of (n) is called a (n)-approximation algorithm.
A 1-approximation algorithm is optimal, and the larger the ratio, the worse the solution. For many NP-complete problems, constant-factor approximations(i.e. computed clique is always at least half the size of maximum-size clique), Sometimes best known approx ratio grows with n, VERTEX COVER PROBLEM Problem: Given graph G = (V,E), find smallestV ' V u Vor v V or s.t. if (u,v) E, then both. Decision problem is NP-complete (3SAT p VC, Sipser 7.5)
Optimization problem is at least as hard. VERTEX COVER ALGORITHM Here is a trivial 2-approximation algorithm Input is some graph G = (V,E). APPROX-VERTEX-COVER 1: C ; 2: E E 3: while E ; do 4: let (u, v) be an arbitrary edge of E 5: C C {(u, v)} 6: remove from E all edges incident on either u or v 7: end while
VERTEX COVER EXAMPLE b c d a e f Input Graph g
b c d a e f g Optimal result, Size 3
VECTOR COVER ALGORITHM EXAMPLE b c d a e f g
b c d a e f Step 1: choose edge (c,e) Step 2: choose edge (d,g)
b c d a e f Step 3: choose edge (a,b) g
g b c d a e f Result: Size 6
g PROOF Theorem. APPROX-VERTEX-COVER is a poly-time 2-approximation algorithm. Proof. The running time is trivially bounded by O(V * E) (at most |E| iterations, each of complexity at most O(V )). Correctness: C clearly is a vertex cover. PROOF cont. Size of the cover: let A denote set of edges that are picked ({(c, e), (d, g), (a, b)} in example). 1. In order to cover edges in A, any vertex cover, in particular an optimal cover C*, must include at least one endpoint of each edge in A. By construction of the algorithm, no two edges in A share an endpoint
(once edge is picked, all edges incident on either endpoint are removed). Therefore, no two edges in A are covered by the same vertex in C*, and |C*| |A|. 2. When an edge is picked, neither endpoint is already in C, thus |C| = 2|A|. Combining (1) and (2) yields |C| = 2|A| 2|C*| q.e.d MAX CUT PROBLEM Given an undirected graph G (V,E): Separate vertices of G into two disjoint sets S and T, such that number of cut edges is maximum. (Maximization Problem)
Cut edge: An edge between a node in S and a node in T. MAX-CUT ALGORITHM Another 2-approximation algorithm : Given G (V,E) 1- S and T V 2- If moving a single node from S to T, or from T to S increases the number of cut edges, make the move. Repeat 2. 3- Output the number of cut edges. QUESTIONS