# Approximation Algorithms Vertex Cover Problem

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

## Recently Viewed Presentations

• P11011: MOTION-TRACKING SYSTEM FINAL DESIGN REVIEW Brittany Bochette Lindsey Clark Mike Ostertag Maya Ramaswamy Andrei Stihi mike * mike * brittany * brittany * maya * britt The clinic at Naz was closed for their winter break, which impacted how...
• El Origen de la Vida El origen de la vida no es explicado en la teoría de la síntesis moderna de la evolución Sólo se ocupa del cambio en los seres vivos, y no de la creación y los cambios...
• means a legal instrument by which a non-Federal entity purchases property or services needed to carry out the project or program under a Federal award. Understanding the Requirements (cont.) Focus on systems and how they support one another in ensuring...
• Prince Henry the Navigator And his school of navigation at Sagres, Portugal By Deborah L. Hoeflinger "the end of the world where the waters of the ocean boil at sunset". (Roman name for Sagres.) Sagres The exact location of Henry's...
• PP / KJP Geschätzte Fallzahl / Quartal Zahl (nach Koch et al. 2004) West-Ost- Gefälle Süd-Nord-Gefälle > 7 / 100.000 EW 2 - 6.9 / 100.000 EW 0 - 1.9 / 100.000 EW Zu erwartende Entwicklung in den kommenden 10...
• Daniel. Daniel's visions. 4 . beasts. Ram, goat, & little horn. Spiritual conflict. Time of the . end. God is in control
• Back at the Buchanan's home, Tom and Daisy flee Long Island unable to face responsibility for their actions . Plot Summary: The Great Gatsby's Last Illusion . ... Pammy Buchannan-Daisy and Tom's daughter. Themes and Motifs. Eyes .
• Working capital management is the management of the short-term investment and financing of a company. Cash and cash equivalents, inventory, accounts receivable, accounts payable, short-term loans,etc. ... Precautionary motive: To avoid stock-out losses. Stock-out losses . are foregone sales as...