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