EY] E[Y] /expected satisfied clauses =E[∑Y /definition of Y:Y ZiYi ∑iE[Y] /linearity of expectation i Pr[Ci satisfied]/definition of Yi ∑7/8 7 二 m. 8 This means that if we choose assignment randomly,then we can satisfy =7/8 fraction of clauses on average. 11
𝐄 𝑌 𝐄 𝑌 = 𝐄 σ𝑖 𝑌𝑖 = σ𝑖 𝐄[𝑌𝑖 ] = σ𝑖 𝐏𝐫[𝐶𝑖 satisfied] = σ𝑖 7/8 = 7 8 𝑚. // expected # satisfied clauses // definition of 𝑌: 𝑌 = σ𝑖 𝑌𝑖 // linearity of expectation // definition of 𝑌𝑖 11 ◼ This means that if we choose assignment randomly, then we can satisfy ≥ 7/8 fraction of clauses on average
Success probability of one assignment We've seen the average number of satisfied clauses on a random assignment. Now we translates this to the average running time of the algorithm? event "success":A random assignment satisfies =7/8 fraction of clauses, We want to estimate the probability p of success. 12
Success probability of one assignment ◼ We’ve seen the average number of satisfied clauses on a random assignment. ◼ Now we translates this to the average running time of the algorithm? ◼ event “success”: A random assignment satisfies ≥ 7/8 fraction of clauses, ◼ We want to estimate the probability 𝑝 of success. 12
Getting a Las Vegas algorithm m-EY]kPr[y= ≤pm+(1-p)(gl-1） ≤pm+(1-p)(Tg-) Rearranging,we get p≥。 8m If we repeatedly take random assignments,it needs 8m times (on average)to see a “success”happening. i.e.the complexity of this Las Vegas algorithm is 8m. 13
Getting a Las Vegas algorithm ◼ 7𝑚 8 = 𝐄 𝑌 = σ𝑘=1 𝑚 𝑘 ⋅ 𝐏𝐫[𝑌 = 𝑘] ≤ 𝑝𝑚 + 1 − 𝑝 7𝑚 8 − 1 ≤ 𝑝𝑚 + 1 − 𝑝 7𝑚 8 − 1 8 ◼ Rearranging, we get 𝑝 ≥ 1 8𝑚 . ◼ If we repeatedly take random assignments, it needs ≤ 8𝑚 times (on average) to see a “success” happening. ❑ i.e. the complexity of this Las Vegas algorithm is ≤ 8𝑚. 13
derandomization We can derandomize the algorithm to get a deterministic one. Previous: Eaefo,1n [of satisfied clauses]>7m/8. ldea:Find an a achieving 7m/8 bit-by-bit Suppose that a1,...,ai-1 are found. ■Key:Eaian∈fo,ly[#of satisfied clauses]is computable in polynomial time. 0 Simplify the formula by inserting a,...,ai-1 Compute the above expectation by E[i Yi]=i E[Yi] 14
derandomization ◼ We can derandomize the algorithm to get a deterministic one. ◼ Previous: 𝐄𝑎∈ 0,1 𝑛 # of satisfied clauses ≥ 7𝑚/8. ◼ Idea: Find an 𝑎 achieving 7𝑚/8 bit-by-bit. ◼ Suppose that 𝑎1 ,… , 𝑎𝑖−1 are found. ◼ Key: 𝐄𝑎𝑖 ,…,𝑎𝑛∈ 0,1 # of satisfied clauses is computable in polynomial time. ❑ Simplify the formula by inserting 𝑎1 , … , 𝑎𝑖−1 ❑ Compute the above expectation by 𝐄 σ𝑖 𝑌𝑖 = σ𝑖 𝐄[𝑌𝑖 ] 14
Example 2:Approximation algorithm for Vertex Cover 15
Example 2: Approximation algorithm for Vertex Cover 15