Class Note for CMPSCI 601 at UMass(23)
Class Note for CMPSCI 601 at UMass(23)
Popular in Course
Popular in Department
This 22 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 13 views.
Reviews for Class Note for CMPSCI 601 at UMass(23)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CMPSCI 601 Recall From Last Time Lecture 20 The following problems are NP Complete 0 SAT 0 3SAT 0 3COLOR 0 CLIQUE 0 Subset Sum 0 Knapsack Knapsack Given n objects object 01 02 on weight 1121 mg mm 20 value 111 v2 on W max weight I can carry in my knapsack Optimization Problem chooseS g 1n to maximize 2 vi z39ES such that 2 mi 3 W z39ES Decision Problem Given 11717 W V can I get total value 2 V while total weight is 3 W Proposition 201 Khapsack is NPComplete Proof Let I 2 m1 mm T be an instance of Subset Sum Problem ENS g 1nZSmi 2 T i6 LetfI 2 m1 mmml mnTTgt be aninstance ofKnapsack Claim I E Subset Sum 42 f I E Knapsack Fact 202 Even though Khapsack is NPComplete there is an e icieht dynamic programming algorithm that can closely approximate the maximum possible V CMPSCI 601 Approximability Lecture 20 Fact NPcomplete decision problems are all equiva lent Belief NPcomplete problems require exponential time in the worst case Fact Dif culty of NP Approximation problems varies Widely De nition 203 A is an NPoptz mz zatl on problem iff 0 For each instance as n 2 lac g 2pm is the set of feasible solutions We can test in P Whether 8 E F 0 Each 8 E has a cost 08 6 Z The cost 08 is computable in F For minimization problems OPTa 2 Sang 08 For maximization problems OPTa 2 833 08 A De nition 204 Let M be a polynomialtime algorithm st on any instance as M is an eapproximation algorithm iff for all as 1004730 OPTW maxOPTarcMar 3 6 4 Oltelt1 e 2 01 is an excellent approximation Minimization problems at most times optimal Maximization prob lems at least 99 percent of optimal e 2 Minimization problems no more than twice opti mal Maximization problems at least half optimal e 2 99 not a very good approximation Minimization problems at most 100 times more than optimal Maxi mization problems at least one percent of optimal Four Classes of NP Optimization Problems INAPPROX E n0 PTIME eapprox alg if P g NP E 36162 O lt 61 lt 62 lt exists PTIME eggapprox alg n0 PTIME elapprox alg if P g NP PTAS E V6 gt OeXists PTIME eapprox alg FPTAS E V6 gt OeXists uniform eapprox alg running in time p01yn FPTAS stands for Fully PolynomialTime Approxima tion Scheme Clique TSP INAPPROX exists P appmx algfar n0 8 lt 1 MAX SAT ATSP VerteXCover APPROX same but nat all 8lt I PT As ETSP all 8lt I Kn apsac poly in n 18 CMPSCI 601 Vertex Cover Lecture 20 Input an undirected graph G 2 V Output min size 0 C V st 0 touches every edge Greedy nodes of high degree About log n times opti mal in the example above There are about n log n total nodes the n fat ones are a vertex cover but the greedy algorithm takes most of the others rst Better Find a Maximal Matching l C 2 Z 2 while E 5 d0 3 pick um E E 4 C 2 C U um 5 delete u 11 from G The edges picked are a maximal matching a disjoint set of edges to which we can t add another disjoint edge If there are m edges in this matching we ve used 2m nodes in C but any algorithm would have to use at least m C 3 2opt G e 2 1 Best known approx ratio 2 10 A Hamilton circuit for an undirected graph G is a cycle that starts and ends at some vertex v and visits every other vertex exactly once HC 2 G I G has a Hamilton Circuit Fact 205 HC is NPComplete Nicest proof is in Sipser TSP 2 G 2 V EwL I Ghas aHC ofweight g L G 2 V E n 2 IV let MG 2 Vi EL11101321 n 1 ifuv E E w uv 2 h 72106 otherwise Observation 206 For any undirected graph G G 6 HC 42gt MG 6 TSP Corollary 207 If TSP has a polynomialtime e approximation algorithm for any 6 lt 1 then P NP Thus TSP E INAPPROX ll G VE n 1V let 80 2 V 9019136 2 70106 1000000 1mm 6 E we uv 2 1000001 otherw1se Let FairTSP be the subset of TSP st no edge weight is more than 00001 percent more than any other edge weight Observation 208 For any undirected graph G G 6 HC 42gt 8G E TSP 42gt 89 6 Fair TSP Observation 209 FairTSP is NPcomplete as a decision problem and as an Optimization problem it has a polynom ial time 10396appr0ximati0n algorithm 12 i Vk J ATSP an k g 4239 339 dj k Claim 2010 Minimum Spanning Tree is a lower bound for ATSP CMST g CATSP Proof Visualize optimal tour Delete one edge and we have a spanning tree A 13 Theorem 2011 cMST g CATSP g 2cMST Proof The multigraph 2MST made by taking two copies of each edge in the tree is connected and all its nodes have even degree Thus it has an Euler s tour providing an e 2 approxi mation algorithm A 14 Aside A multigraph G 2 V E is a graph except that E may be a multiset ie there can be more than one edge between a certain pair of vertices An Euler s Tour of an undirected multigraph G is a tour that starts and ends at the same vertex and traverses each edge exactly once Fact G has an Euler s tour iff G is connected and each vertex of G has even degree If G has an Euler s tour then such a tour can be computed in linear time 15 Christo des Algorithm 1976 In the MST only worry about the odd degree nodes There are an even number of vertices of odd degree In polynomial time we can nd a minimum weight per fect matching M on the odddegree nodes MST UM is an Eulerian graph MST g TSP M g grsn Thus we get a tour at most 15 times optimal e 2 g 16 Euclidean TSP ETSP Euclidean distance in plane Wm 31 56 y 50 50 y 31 ETSP has a PolynomialTime Approximation Scheme PTAS Arora 1997 17 CMPSCI 601 Interactive Proofs Lecture 20 Il X readonly input nite 039 random bits control H Proof work tape MerlinArthur games MA Babai Decision problem D input string 3 Merlin Prover chooses the polynomiallength string H that Maximizes the chances of convincing Arthur that a is an element of D Arthur Veri er computes the Average value of his possible computations on H as Arthur is a polynomial time probabilistic Turing machine 18 De nition 2012 We say that A accepts D iff the follow ing conditions hold 1 If a E D there exists a proof H39 such that A accepts for every random string a Pro A az a 2 Accept 2 1 2 If a gZ D for every proof H A rejects for most of the random strings a Pro AH a 2 Accept lt i 19 Any decision problem D E NP has a deterministic polynomial time veri er satisfying De nition 2012 By adding randomness to the veri er we can greatly re strict its computational power and the number of bits of H that it needs to look at while still enabling it to accept all of NP We say that a veri er A is r02 qnrestricted iff for all inputs of size n and all proofs H A uses at most Orn random bits and examines at most Oqn bits of its proof H Let PCPrn be the set of boolean queries that are accepted by r01 qnrestricted veri ers Fact 2013 PCP Theorem NP 2 PCPlogn 1 The proof of this theorem is pretty messy certainly more than we can deal with here But we can look at the appli cations of the PCP Theorem to approximation problems 20 MAXBSAT given a 3CNF formula nd a truth as signment that maximizes the number of true clauses x1 V932 V927 x1 V324 V927 aT1aTgaT4 xQVaTgvm aT2933a5 mvmvm KVTQVasg Vacjvm Proposition 2014 MAXBSAT has a polynomialtime e 2 approximation algorithm Proof Be greedy set each variable in turn to the better value A You can do better a random assignment gets 78 of the clauses Open for Years Assuming NP 7 P is there some 6 O lt 6 lt 1 st MAXBSAT has no PTIME eapproximation algorithm 21 Theorem 2015 The PCP theorem NP 2 PCPlog n 1 is equivalent to the fact that If P NP then Forsome e1gt e gt O MAXBSAT has no polynomialtime eapproximation algorithm Fact 2016 MAXBSAT has a PTIME approximation algorithm with e 2 i and no better ratio can be achieved unless P 2 NP References 0 Approximation Algorithms for NP Hara Problems Dorit Hochbaum 6d PWS 1997 0 Juraj Hromkovic Algorithmics for Hard Problems Springer 2001 0 Sanjeev Arora The Approximability ofNPhard Prob lems STOC 98 wwwcsprincetoneduNarora 22
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'