CSC3160: Design and Analysis of Algorithms Week 11: Approximation Algorithms Instructor: Shengyu Zhang 1
Instructor: Shengyu Zhang 1
Optimization Very often we need to solve an optimization problem. Maximize the utility/payoff/gain/... Minimize the cost/penalty/loss/... Many optimization problems are NP-complete No polynomial algorithms are known,and most likely,they don't exist. More details in the previous lecture. ■ Approximation:get an approximately good solution. 2
Optimization ◼ Very often we need to solve an optimization problem. ❑ Maximize the utility/payoff/gain/… ❑ Minimize the cost/penalty/loss/… ◼ Many optimization problems are NP-complete ❑ No polynomial algorithms are known, and most likely, they don’t exist. ❑ More details in the previous lecture. ◼ Approximation: get an approximately good solution. 2
Example 1:A simple approximation algorithm for 3SAT 3
Example 1: A simple approximation algorithm for 3SAT 3
SAT ■3SAT: ▣ n variables:x1,...,xnE {0,1} m clauses:OR of 3 variables or their negations ■e.g.x1Vx2Vx3 CNF formula:AND of these m clauses x=10010 ■E.g.φ=(x1Vx2Vx3)∧(x2Vx4Vx)∧(x1Vx3Vx) 3SAT Problem:Is there an assignment of variables x s.t.the formula o evaluates to 1? i.e.assign a 0/1 value to each xi to satisfy all clauses. 4
SAT ◼ 3SAT: ❑ 𝑛 variables: 𝑥1,… , 𝑥𝑛 ∈ 0,1 ❑ 𝑚 clauses: OR of 3 variables or their negations ◼ e.g. 𝑥1 ∨ 𝑥2 ∨ 𝑥3 ❑ CNF formula: AND of these 𝑚 clauses ◼ E.g. 𝜙 = 𝑥1 ∨ 𝑥2 ∨ 𝑥3 ∧ 𝑥2 ∨ 𝑥4 ∨ 𝑥5 ∧ 𝑥1 ∨ 𝑥3 ∨ 𝑥5 ◼ 3SAT Problem: Is there an assignment of variables 𝑥 s.t. the formula 𝜙 evaluates to 1? ❑ i.e. assign a 0/1 value to each 𝑥𝑖 to satisfy all clauses. 4 𝑥 = 10010
Hard 3SAT is known as an NP-complete problem. Very hard:no polynomial algorithm is known. Conjecture:no polynomial algorithm exists. If a polynomial algorithm exists for 3SAT,then polynomial algorithms exist for all NP problems. More details in last lecture. 5
Hard ◼ 3SAT is known as an NP-complete problem. ❑ Very hard: no polynomial algorithm is known. ❑ Conjecture: no polynomial algorithm exists. ❑ If a polynomial algorithm exists for 3SAT, then polynomial algorithms exist for all NP problems. ◼ More details in last lecture. 5
7/8-approximation of 3SAT Since 3SAT appears too hard in its full generality,let's aim lower. 3SAT asks whether there is an assignment satisfying all clauses. ■ Can you find an assignment satisfying half of the clauses? Let's run an example where you give an input instance you give a solution! 6
7/8-approximation of 3SAT ◼ Since 3SAT appears too hard in its full generality, let’s aim lower. ◼ 3SAT asks whether there is an assignment satisfying all clauses. ◼ Can you find an assignment satisfying half of the clauses? ◼ Let’s run an example where ❑ you give an input instance ❑ you give a solution! 6
Observation What did we just do? How did we assign values to variables? For each variable xi,we choose a number from {0,1}. How good is this assignment? Result:out 5;out 5
Observation ◼ What did we just do? ◼ How did we assign values to variables? ◼ For each variable 𝑥𝑖 , we ___ choose a number from {0,1}. ◼ How good is this assignment? ❑ Result: __ out 5; __ out 5. 7
Why? For each clause,there are 8 possible assignments for these three variables,and only 1 fails. ▣ E.g.x1V x2 Vx3:only (x1,x2,x3)=(0,0,0)fails. E.g.V x2Vx3:only (x1,x2,x3)=(1,0,1)fails. Thus if you assign randomly,then with each clause fails with probability only 1/8. Thus the expected number of satisfied clauses is 7m/8. ▣ m:number of clauses 8
Why? ◼ For each clause, there are 8 possible assignments for these three variables, and only 1 fails. ❑ E.g. 𝑥1 ∨ 𝑥2 ∨ 𝑥3: only 𝑥1, 𝑥2, 𝑥3 = (0,0,0) fails. ❑ E.g. 𝑥1 ∨ 𝑥2 ∨ 𝑥3 : only 𝑥1, 𝑥2, 𝑥3 = (1,0,1) fails. ◼ Thus if you assign randomly, then with each clause fails with probability only 1/8. ◼ Thus the expected number of satisfied clauses is 7𝑚/8. ❑ 𝑚: number of clauses 8
Formally-algorithm Repeat Pick a random a e {0,17. See how many clauses the assignment x a satisfies. Return a if it satisfies 7m/8 clauses. This is a Las Vegas algorithm: The running time is not fixed.It's a random variable. 口 When the algorithm terminates,it always gives a correct output. The complexity measure is the expected running time. 9
Formally - algorithm ◼ Repeat Pick a random 𝑎 ∈ 0,1 𝑛 . See how many clauses the assignment 𝑥 = 𝑎 satisfies. Return 𝑎 if it satisfies ≥ 7𝑚/8 clauses. ◼ This is a Las Vegas algorithm: ❑ The running time is not fixed. It’s a random variable. ❑ When the algorithm terminates, it always gives a correct output. ❑ The complexity measure is the expected running time. 9
Formally-analysis Define a random variable Y for each clause i. If clause i is satisfied,then Yi 1,otherwise Yi 0. Define another random variable Y =i Yi Y has a clear meaning:number of satisfied clauses What's expectation of Y? 10
Formally - analysis ◼ Define a random variable 𝑌𝑖 for each clause 𝑖. ❑ If clause 𝑖 is satisfied, then 𝑌𝑖 = 1, otherwise 𝑌𝑖 = 0. ◼ Define another random variable 𝑌 = σ𝑖 𝑌𝑖 ❑ 𝑌 has a clear meaning: number of satisfied clauses ◼ What’s expectation of 𝑌? 10