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) 0<a<1 minimization problems VI,S(I)≤a·OPT(I) Q>1
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