×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

19

0

22

# Class Note for CMPSCI 601 at UMass(22)

Marketplace > University of Massachusetts > Class Note for CMPSCI 601 at UMass 22

No professor available

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
No professor available
TYPE
Class Notes
PAGES
22
WORDS
KARMA
25 ?

## 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 19 views.

×

## Reviews for Class Note for CMPSCI 601 at UMass(22)

×

×

### What is Karma?

#### 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 21 To prove A is NPcomplete 0 Prove A E NP 0 Prove B 3 A where B is known to be NPcomplete The following problems are NPComplete 0 SAT CookLevin Theorem 0 3SAT 0 3COLOR 0 CLIQUE 0 Subset Sum 0 Knapsack decision version 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 Z 211239 3 W z39es Decision Problem Given 11717 W V can I get total value 2 V while total weight is 3 W Proposition 211 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 lt2 f I E Knapsack Fact 212 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 21 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 213 A is an NPoptz mz zatl on problem iff 0 For each instance as n 2 19 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 214 Let M be a polynomialtime algorithm st on any instance as M is an eapproximation algorithm iff for all as 10M OPTW maxOPTarcMar S 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 21 Input an undirected graph G 2 V Output a minimum size 0 C V such that C 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 G has a Hamilton Circuit Fact 215 HC is NPComplete Nicest proof is in Sipser TSP 2 G 2 V EwL Ghas aHC ofweight g L G 2 V E n 1V1716thla V EL11101321 n 1 ifuv E E w uv 2 h 72106 otherwise Observation 216 For any undirected graph G G 6 HC lt2 MG 6 TSP Corollary 217 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 218 For any undirected graph G G E HC 42gt 8G E TSP 42gt 89 E Fair TSP Observation 219 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 TSP where dz k g dij dj 1 Claim 2110 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 2111 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 21 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 2112 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 4 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 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 2113 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 2114 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 2115 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 2116 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

×

×

### BOOM! Enjoy Your Free Notes!

×

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'

## Why people love StudySoup

Jim McGreen Ohio University

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Allison Fischer University of Alabama

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over \$600 per month. I LOVE StudySoup!"

Bentley McCaw University of Florida

Forbes

#### "Their 'Elite Notetakers' are making over \$1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com