MAX-SAT nstance:a set of clauses ●Boolean variables: X1,X2,,n C1=(x1V7x2V一X3) C2=（7x1V7X3) ●literal:Xi,xi C3=(x1V X2VX4) clause:OR of literals C4=(x4V一x3) ●MAX-SAT C5=(x4Vx1) ●NP-hard Solution:a truth assignment maximizing of satisfied clauses
MAX-SAT • Boolean variables: • literal: • clause: OR of literals • MAX-SAT • NP-hard Instance: a set of clauses Solution: a truth assignment maximizing # of satisfied clauses x1,x2,...,xn xi ,¬xi C1 = (x1 ¬x2 ¬x3) C2 = (¬x1 ¬x3) C3 = (x1 x2 x4) C4 = (x4 ¬x3) C5 = (x4 ¬x1)
Approximation Algorithms maximization problems Fix a problem instance (input)I: optimal solution:OPT(I) solution returned by Alg:S(T) I,S(I)≥a·OPT() a-approximation algorithm
Fix a problem instance (input) I: • optimal solution: OPT(I) • solution returned by Alg: S(I) Approximation Algorithms maximization problems α-approximation algorithm I, S(I) · OPT(I)
Approximation Algorithms a-approximation algorithm maximization problems VI,S()≥a·OPT(I) 01
Approximation Algorithms α-approximation algorithm maximization problems minimization problems I, S(I) · OPT(I) > 1 I, S(I) · OPT(I) 0 < < 1
Randomized Approximation Instance:a set of m clauses Solution:a truth assignment maximizing of satisfied clauses assign each variable with true or false uniformly and independently at random a clause C=(iv2 v...vek) ljefxi,xi} 1 Pr[C is satisfied ]=1-2-k ≥ -2 linearity of expectation E[satisfied clauses ] 2
Randomized Approximation Instance: a set of m clauses assign each variable with true or false uniformly and independently at random Solution: a truth assignment maximizing # of satisfied clauses a clause C = (1 2 ···k ) j {xi ,¬xi} Pr[C is satisfied ] = 12k 1 2 E[ # satisfied clauses ] m 2 linearity of expectation
Randomized Approximation Instance:a set of m clauses Solution:a truth assignment maximizing of satisfied clauses assign each variable with true or false uniformly and independently at random E[satisfied clauses n 2 ≥ 2OPT OPT≤m
Randomized Approximation Instance: a set of m clauses assign each variable with true or false uniformly and independently at random Solution: a truth assignment maximizing # of satisfied clauses OPT ≤ m E[ # satisfied clauses ] m 2 1 2 OPT
Integer Programming boolean variables:X1,x2,...,xn 1 if xi=true )if xi=false truth assignment→ye{0,l}” a clause C=(1v2v...vek) ljefxi,xib C+:set of i that xi is in C C:set of i that xi is in C C is satisfied (1-)≥1 i∈C+ i∈C-
Integer Programming a clause C = (1 2 ···k ) j {xi ,¬xi} C + : C : yi = 1 if xi = true 0 if xi = false set of i that xi is in C set of i that ¬xi is in C truth assignment y {0, 1}n boolean variables: x1,x2,...,xn C is satisfied iC+ yi + iC (1 yi) 1
Integer Programming boolean variables:x1,x2,...,xn clauses: C1,C2,.,Cm m maximize ∑ j=1 subject to ∑+∑(1-)≥，1≤j≤m icC时 iECj yE{0,1 V1≤i≤n e{0,1} V1≤j≤m integral solution
maximize m j=1 zj subject to iC+ j yi + iC j (1 yi) ⇤ zj , ⇧1 ⇥ j ⇥ m yi ⌅ {0, 1}, ⇧1 ⇥ i ⇥ n zj ⌅ {0, 1}, ⇧1 ⇥ j ⇥ m Integer Programming clauses: C1, C2,...,Cm boolean variables: x1,x2,...,xn integral solution
Linear Programming boolean variables:X1,x2,...,xn clauses: C1,C2,.,Cm maximize ∑ j=1 subject to ∑%+∑(1-)≥2,1≤j≤m ieC时 ieC明 ∈[0,1]， V1≤i≤n ∈[0,1]， V1≤j≤m LP-relaxation
maximize m j=1 zj subject to iC+ j yi + iC j (1 yi) ⇤ zj , ⇧1 ⇥ j ⇥ m yi ⌅ {0, 1}, ⇧1 ⇥ i ⇥ n zj ⌅ {0, 1}, ⇧1 ⇥ j ⇥ m Linear Programming clauses: C1, C2,...,Cm boolean variables: x1,x2,...,xn LP-relaxation [ [ ] ]
Rounding LP Relaxation represent the problem as an IP; ●relax the IP to an LP; solve the LP fractionally in poly-time; round the fractional optimal solution to an integer feasible solution. Randomized rounding!
Rounding LP Relaxation • represent the problem as an IP; • relax the IP to an LP; • solve the LP fractionally in poly-time; • round the fractional optimal solution to an integer feasible solution. Randomized rounding!
LP Relaxation maximize j=1 subject to ∑+∑(1-)≥，1≤j≤m ieC时 iECj 0≤yi≤1， V1≤i≤n 0≤1≤1， V1≤j≤m y,:optimal fractional solution E [0,1] m OPT≤烤 0=1
LP Relaxation maximize m j=1 zj subject to iC+ j yi + iC j (1 yi) ⇤ zj , ⌅1 ⇥ j ⇥ m 0 ⇥ yi ⇥ 1, ⌅1 ⇥ i ⇥ n 0 ⇥ zj ⇥ 1, ⌅1 ⇥ j ⇥ m y i , z j : optimal fractional solution ∈ [0,1] OPT m j=1 z j