南京大学：《随机算法 Randomized Algorithms》课程教学资源（课件讲稿）Random Rounding

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 ] = 1￾2￾k ￾ 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 ￾ i￾C+ yi + ￾ i￾C￾ (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 ￾ i￾C+ j yi + ￾ i￾C￾ 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 ￾ i￾C+ j yi + ￾ i￾C￾ 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 ￾ i￾C+ j yi + ￾ i￾C￾ 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