香港中文大学：《Topics in Theoretical Computer Science》课程教学资源（PPT课件讲稿）Lecture 4 Approximation algorithms

CMS57opomtr cince Week 4:Approximation Algorithms Instructor:Shengyu Zhang

Instructor: Shengyu Zhang 1

Optimization Very often we need to solve an optimization problem. Maximize the utility/payoff/gain/... 0 Minimize the cost/penalty/loss/... Many optimization problems are NP-complete No polynomial algorithms are known,and most likely,they don't exist. Question:Do you want more of this topic? ■ 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. ❑ Question: Do you want more of this topic? ◼ 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: ▣1 m variables:x1,…,xn∈{0,1} ▣ m clauses:OR of exactly 3 variables or their negations ■e.g.x1Vx2Vx3 x=10010 CNF formula:AND of these m clauses ■E.g.中=(Vx2Vx3)∧(x2Vx4Vx5)∧(x1Vx3Vx5) 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 exactly 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