Randomized Algorithms
2C0SC213-7034W-07inter 2021 – Sam Toueg CSC373 Winter 2021 1
Randomized Algorithms
You already saw at least two such algorithms:
• Quicksort: 𝑂(𝑛𝑙𝑜𝑔𝑛) expected running time
• Order Statistics Select(𝐴,𝑘) : 𝑂(𝑛) expected running time
2C0SC213-7034W-07inter 2021 – Sam Toueg CSC373 Winter 2021 2
Revisiting Exact Max-𝑘-SAT
2C0SC213-7034W-07inter 2021 – Sam Toueg 3
Exact Max-𝑘-SAT
• Problem
Ø Input: An 𝑘-CNF formula 𝜑 = 𝐶! ∧ 𝐶” ∧ ⋯ ∧ 𝐶# each clause 𝐶$ has exactly 𝑘 literals
each clause 𝐶$ has a weight 𝑤$ ≥ 0
Ø Output: A truth assignment 𝜏 that maximizes the number (or total weight) of clauses satisfied under 𝜏
Example: 3-CNF formula
𝜑=𝑥̅∨𝑥∨𝑥̅ ∧𝑥∨𝑥∨𝑥 ∧𝑥̅∨𝑥∨𝑥 ∧𝑥∨𝑥∨𝑥̅
!”#!”$”$#!”$
Recall: a literal is a variable 𝑥 or its negation 𝑥̅ %%
2021-04-07 CSC373 Winter 2021 – Sam Toueg 9
Exact Max-𝑘-SAT
• Problem
Ø Input: An 𝑘-CNF formula 𝜑 = 𝐶! ∧ 𝐶” ∧ ⋯ ∧ 𝐶# each clause 𝐶$ has exactly 𝑘 literals
each clause 𝐶$ has a weight 𝑤$ ≥ 0
Ø Output: A truth assignment 𝜏 that maximizes the number (or total weight) of clauses satisfied under 𝜏
• Max-2-SAT is NP-hard (we did not prove this)
2021-04-07 CSC373 Winter 2021 – Sam Toueg 10
Exact Max-𝑘-SAT
• Problem
Ø Input: An 𝑘-CNF formula 𝜑 = 𝐶! ∧ 𝐶” ∧ ⋯ ∧ 𝐶# each clause 𝐶$ has exactly 𝑘 literals
each clause 𝐶$ has a weight 𝑤$ ≥ 0
Ø Output: A truth assignment 𝜏 that maximizes the number (or total weight) of clauses satisfied under 𝜏
• We proved:
Ø There is a local search “⁄ -apx algo for Exact Max-2-SAT
• We claimed (without proof):
Ø There is a local search %⁄ -apx algo for Exact Max-2-SAT
Ø It can be generalized to a “!’! -apx for Exact Max-𝑘-SAT “!
o This algorithm is much more complicated
2021-04-07 CSC373 Winter 2021 – Sam Toueg 11
%
&
Exact Max-𝑘-SAT
• Problem
Ø Input: An 𝑘-CNF formula 𝜑 = 𝐶! ∧ 𝐶” ∧ ⋯ ∧ 𝐶# each clause 𝐶$ has exactly 𝑘 literals
each clause 𝐶$ has a weight 𝑤$ ≥ 0
Ø Output: A truth assignment 𝜏 that maximizes the number (or total weight) of clauses satisfied under 𝜏
• What can we do with randomized algorithms?
• Now we want to maximize the expected number
(or total weight) of satisfied clauses
2021-04-07 CSC373 Winter 2021 – Sam Toueg 12
Exact Max-𝑘-SAT
• Problem
Ø Input: An 𝑘-CNF formula 𝜑 = 𝐶! ∧ 𝐶” ∧ ⋯ ∧ 𝐶# each clause 𝐶$ has exactly 𝑘 literals
each clause 𝐶$ has a weight 𝑤$ ≥ 0
Ø Output: A truth assignment 𝜏 that maximizes the number (or total weight) of clauses satisfied under 𝜏
• Let’s try the most naïve randomized algorithm:
Ø Set each variable to TRUE with probability 1⁄2, and
FALSE with probability 1⁄2
• How good is this?
2021-04-07 CSC373 Winter 2021 – Sam Toueg 13
Exact Max-𝑘-SAT – Randomized algorithm
• We have:
Ø 𝜑 = 𝐶! ∧ 𝐶” ∧ ⋯ ∧ 𝐶& with weights 𝑤!, 𝑤”, … , 𝑤& Ø Each 𝐶’ contains exactly 𝑘 literals
• Randomizedtruthassignment𝜏:
Ø Set each variable to TRUE with probability 1⁄2, and FALSE with probability 1⁄2
• For each clause 𝐶’:
Ø Pr[𝐶’ is not satis9ied] = (1/2) (because 𝐶’ has exactly 𝑘 literals)
(1/2)(
Ø Pr[𝐶’ is satis9ied] = 1 − (1/2)( = (2(−1)/2(
Ø Let 𝑊’ be the weight that we get from 𝐶’ under truth assignment 𝜏: o𝑊’ is𝑤’ if𝜏satisfies𝐶’,anditis0if𝜏doesnotsatisfy𝐶’
oSo:𝐸 𝑊’ = 𝑤’ ⋅Pr 𝐶’ issatis9ied +0⋅Pr[𝐶’ isnotsatis9ied] oSo:𝐸𝑊’ =𝑤’⋅(2(−1)/2(
CSC373 Winter 2021 – Sam Toueg 14
Exact Max-𝑘-SAT – Randomized algorithm
• We have:
Ø 𝜑 = 𝐶! ∧ 𝐶” ∧ ⋯ ∧ 𝐶& with weights 𝑤!, 𝑤”, … , 𝑤& Ø Each 𝐶’ contains exactly 𝑘 literals
• Randomizedtruthassignment𝜏:
Ø Set each variable to TRUE with probability 1⁄2, and FALSE with probability 1⁄2
• For each clause 𝐶’:
Ø Pr[𝐶’ is not satis9ied] = (1/2)( (because 𝐶’ has exactly 𝑘 literals)
Ø Pr[𝐶’ is satis9ied] = 1 − (1/2)( = (2(−1)/2(
Ø Let 𝑊’ be the weight that we get from 𝐶’ under truth assignment 𝜏: Ø𝐸𝑊’ =𝑤’⋅(2(−1)/2(
• Let 𝑊 = the total weight of all the clauses that are satisfied
Ø 𝑊 = 𝑊! + 𝑊” + ⋯ + 𝑊& By linearity of expectations!
Ø𝐸𝑊=𝐸𝑊+𝑊+⋯+𝑊 =∑& 𝐸𝑊 &! “( (& ‘)! ‘
Ø 𝐸[𝑊] = ∑’)! 𝑤’ ⋅ (2 −1)/2 Ø𝐸[𝑊]=”!*!⋅∑& 𝑤 ≥2″ −1⋅𝑂𝑃𝑇
“! ‘)!’ 2″
CSC373 Winter 2021 – Sam Toueg 15
𝐸[𝑊] ≥ )!*+ ⋅ 𝑂𝑃𝑇 !! )!
Derandomization
• We saw a simple randomized approximation algorithm that gives a very good result:
𝐸[𝑊] ≥ )!*+ ⋅ 𝑂𝑃𝑇 )!
• Can we “derandomize’’ it?
Ø The algorithm is making some random choices, and sometimes
they turn out to be good
Ø Can we make these “good” choices deterministically?
2C0SC213-7034W-07inter 2021 – Sam Toueg CSC373 Winter 2021 22
Derandomization
• What are the random choices made by this algorithm? Ø Setting the values of the boolean variables 𝑥!, 𝑥”, … , 𝑥(
• How do we know which set of choices is good?
• Idea:
Ø Do not think about all the choices at once
Ø Do them successively one by one:
o First find a good choice for 𝑥! where only 𝑥”, … , 𝑥+ are “random’’
o Then find a good choice for 𝑥” where only 𝑥$, … , 𝑥+ are “random’’ o……
o Finally find a good choice for 𝑥+
2C0SC213-7034W-07inter 2021 – Sam Toueg CSC373 Winter 2021 23
Derandomization
• Let 𝑊(𝜏) be the total weight of the clauses of 𝜑 satisfied under random 𝜏 for 𝑥”, 𝑥#, … , 𝑥$
• Weprovedthat𝐸𝑊𝜏 ≥#!%”⋅𝑂𝑃𝑇 #!
• Say you want to:
Ø deterministically make the right choice for 𝑥” Ø and keep the choice for 𝑥#, … , 𝑥$ random
•Notethat:𝐸𝑊𝜏 =Pr𝑥”=𝑇⋅𝐸𝑊𝜏 𝑥”=𝑇+ Pr𝑥”=𝐹⋅𝐸𝑊𝜏 𝑥”=𝐹
•So:𝐸𝑊𝜏 =”⁄⋅𝐸𝑊𝜏 𝑥=𝑇+”⁄⋅𝐸𝑊𝜏 𝑥=𝐹 #”#”
• Thus:atleastoneof𝐸 𝑊 𝜏 𝑥”=𝑇 and𝐸 𝑊 𝜏 𝑥”=𝐹 must be greater than or equal to 𝐸 𝑊 𝜏
• Idea: compute both (we will later see how), and take the better of the two! This gives an expected total weight at least as good as 𝐸 𝑊 𝜏 !
• Thatis:set𝑥” =𝑣∈{𝑇,𝐹} suchthat𝐸 𝑊 𝜏 𝑥”=𝑣]≥𝐸 𝑊 𝜏 𝑥” =𝑣̅]
• This deterministic setting of 𝑥” (together with the random choice for 𝑥# , … , 𝑥$ )
Ø gives an expected total weight at least as good as 𝐸 𝑊 𝜏 Ø So the expected total weight is still ≥ #!%” ⋅ 𝑂𝑃𝑇
#!
2C0SC213-7034W-07inter 2021 – Sam Toueg CSC373 Winter 2021 25
Derandomization
• Once we have made the right choice for 𝑥! (say 𝑥!= 𝑇), then we
can apply the same method to select the value of 𝑥”: 𝐸𝑊𝜏|𝑥=𝑇=1N⋅𝐸𝑊𝜏 𝑥=𝑇,𝑥=𝑇
!12!” +N⋅𝐸𝑊𝜏 𝑥=𝑇,𝑥=𝐹
2
Ø Then pick the value of 𝑥” that gives a better expectation
!”
ØCompute𝐸 𝑊 𝜏 𝑥! =𝑇,𝑥” =𝑇 and𝐸 𝑊 𝜏 𝑥! =𝑇,𝑥” =𝐹
• Derandomized Algorithm:
Ø For 𝑖 = 1, … , 𝑛 {* deterministically chose the value of 𝑥$ *}
oif𝐸 𝑊 𝜏 𝑥! =𝑣!,𝑥” =𝑣”,…,𝑥’*! =𝑣’*!,𝑥’ =𝑇 ≥ 𝐸 𝑊 𝜏 𝑥!= 𝑣!,𝑥” = 𝑣”,…,𝑥’*! = 𝑣’*!,𝑥’ = 𝐹
then𝑣’ =𝑇else𝑣’ =𝐹 oSet𝑥’ =𝑣’
2C0SC213-7034W-07inter 2021 – Sam Toueg CSC373 Winter 2021 28
Derandomization
• Derandomized Algorithm:
Ø For 𝑖 = 1, … , 𝑛 {∗ determinisYcally chose the value of 𝑥$ ∗}
oif𝐸 𝑊 𝜏 𝑥! =𝑣!,𝑥” =𝑣”,…,𝑥’*! =𝑣’*!,𝑥’ =𝑇 ≥ 𝐸 𝑊 𝜏 𝑥! =𝑣!,𝑥” =𝑣”,…,𝑥’*! =𝑣’*!,𝑥’ =𝐹
then𝑣’ =𝑇else𝑣’ =𝐹 oSet𝑥’ =𝑣’
ØWhile the simple randomized algorithm achieves:
ØThe derandomized (deterministic) version above achieves:
ØOk, but…How do we compute the two conditional expectations? 2C0SC213-7034W-07inter 2021 – Sam Toueg CSC373 Winter 2021 30
𝐸[𝑊(𝜏)] ≥ “!*! ⋅ 𝑂𝑃𝑇 “!
𝑊(𝜏) ≥ “!*! ⋅ 𝑂𝑃𝑇 “!
Derandomization
• Tocompute:𝐸 𝑊 𝜏 𝑥!=𝑣!,𝑥” =𝑣”,…,𝑥’*! =𝑣’*!,𝑥’ =𝑇 • Note that this is equal to:
• ∑% 𝑤% ⋅
• Compute this conditional probability for each clause 𝐶% as follows: Ø Set the values of 𝑥!, 𝑥”, … , 𝑥’*! and 𝑥’
to 𝑣!, 𝑣”, … , 𝑣’*! and 𝑇
Ø If 𝐶% is TRUE under this setting, the corresponding probability is 1
Ø If 𝐶% is FALSE under this setting, the corresponding probability is 0
Ø Otherwise, 𝐶% must have l ≥ 1 literals with no truth assignment yet
In this case the corresponding probability that 𝐶% is satisfied is: 1 − (1/2)l • Tocompute:𝐸 𝑊 𝜏 𝑥!=𝑣!,𝑥” =𝑣”,…,𝑥’*! =𝑣’*!,𝑥’ =𝐹
Ø similar to above
2C0SC213-7034W-07inter 2021 – Sam Toueg CSC373 Winter 2021 32
Pr[𝐶% issatis9ied 𝑥!=𝑣!,𝑥” =𝑣”,…,𝑥’*! =𝑣’*!,𝑥’ =𝑇
Derandomized Exact Max-𝑘-SAT approximation algorithm – An example 𝜑= 𝑥̅”∨𝑥# ∧ 𝑥”∨𝑥# ∧ 𝑥̅”∨𝑥$ ∧ 𝑥#∨𝑥̅$ ∧ 𝑥̅#∨𝑥̅$ ∧ 𝑥”∨𝑥̅# ∧ 𝑥̅#∨𝑥$ ∧ 𝑥̅”∨𝑥̅#
Here every 𝐶’ has exactly 𝑘 = 2 literals and has weight 𝑤’ = 1 Recall:
Ø Simple randomized algo = independently set each variable 𝑥’ of 𝜑 to TRUE/FALSE with probability 0.5 each
Ø Simple randomized algo gives:
𝐸[number of saSsfied clauses] ≥ “!*! ⋅ 𝑂𝑃𝑇 = 3/4 ⋅ 𝑂𝑃𝑇
Ø We want to derandomize this algorithm to get:
number of saSsfied clauses ≥ “!*! ⋅ 𝑂𝑃𝑇 = 3/4 ⋅ 𝑂𝑃𝑇
“!
“!
2021-04-07 CSC373 Winter 2021 – Sam Toueg 33
Derandomized Exact Max-𝑘-SAT approximation algorithm – An example 𝜑= 𝑥̅”∨𝑥# ∧ 𝑥”∨𝑥# ∧ 𝑥̅”∨𝑥$ ∧ 𝑥#∨𝑥̅$ ∧ 𝑥̅#∨𝑥̅$ ∧ 𝑥”∨𝑥̅# ∧ 𝑥̅#∨𝑥$ ∧ 𝑥̅”∨𝑥̅#
Since the weight of every clause is 1:
𝑊 𝜏 is just the number of clauses satisfied in 𝜑 under truth assignment 𝜏
Computing𝐸 𝑊 𝜏 𝑥”=𝑇 : Firstset 𝑥” to𝑇in𝜑 𝐸 𝑊 𝜏 𝑥”=𝑇 =23/4 1 +1 +1 +1−1+1−1+1 +1−1+1 =23/4
𝜑=𝑥̅∨𝑥 ∧𝑥∨𝑥 ∧𝑥̅∨𝑥 ∧𝑥∨𝑥̅ ∧𝑥̅∨𝑥̅ ∧𝑥∨𝑥̅ ∧𝑥̅∨𝑥 ∧𝑥̅∨𝑥̅ ∧𝑥∨𝑥 “2# “# “2$ #4$ #4$ “# #4$ “2# “$
𝜑= 𝑥̅”∨𝑥# ∧ 𝑥”∨𝑥# ∧ 𝑥̅”∨𝑥$ ∧ 𝑥#∨𝑥̅$ ∧ 𝑥̅#∨𝑥̅$ ∧ 𝑥”∨𝑥̅# ∧ 𝑥̅#∨𝑥$ ∧ 𝑥̅”∨𝑥̅# TT
Computing𝐸 𝑊 𝜏 𝑥”=𝐹 : Firstset 𝑥” to𝐹in𝜑 𝐸 𝑊 𝜏 𝑥”=𝐹 =25/4 1 + 1 + 1 + 1−1 + 1−1 + 1 + 1−1 + 1 = 25/4
𝜑=𝑥̅∨𝑥 ∧𝑥∨𝑥 ∧𝑥̅∨𝑥 ∧𝑥∨𝑥̅ ∧𝑥̅∨𝑥̅ ∧𝑥∨𝑥̅ ∧𝑥̅∨𝑥 ∧𝑥̅∨𝑥̅ ∧𝑥∨𝑥 “# “2# “$ #4$ #4$ “2# #4$ “# “$
𝜑= 𝑥̅”∨𝑥# ∧ 𝑥”∨𝑥# ∧ 𝑥̅”∨𝑥$ ∧ 𝑥#∨𝑥̅$ ∧ 𝑥̅#∨𝑥̅$ ∧ 𝑥”∨𝑥̅# ∧ 𝑥̅#∨𝑥$ ∧ 𝑥̅”∨𝑥̅# TTT
Since 𝐸 𝑊 𝜏 𝑥”=𝐹 >𝐸 𝑊 𝜏 𝑥”=𝑇 wedeterministicallychose𝑥” tobe𝐹, that is, we set 𝜏(𝑥”) = 𝐹, and then continue to derandomize the choice of 𝑥#
2021-04-07 CSC373 Winter 2021 – Sam Toueg 34
Derandomized Exact Max-𝑘-SAT approximation algorithm – An example The formula 𝜑 after setting 𝑥” to 𝐹 :
𝜑= 𝑥̅”∨𝑥# ∧ 𝑥”∨𝑥# ∧ 𝑥̅”∨𝑥$ ∧ 𝑥#∨𝑥̅$ ∧ 𝑥̅#∨𝑥̅$ ∧ 𝑥”∨𝑥̅# ∧ 𝑥̅#∨𝑥$ ∧ 𝑥̅”∨𝑥̅# Computing𝐸 𝑊 𝜏 𝑥”=𝐹,𝑥# =𝑇 : Set 𝑥# to𝑇 𝐸 𝑊 𝜏 𝑥”=𝐹,𝑥# =𝑇 =6
TTT
1 1 1+1 1 0+1+1=6 𝜑= 𝑥̅”∨𝑥# +∧ 𝑥”∨𝑥# +∧ 𝑥̅”∨𝑥$ ∧ 𝑥#∨𝑥̅$ +∧ 𝑥̅#∨𝑥̅$ +∧ 𝑥”∨𝑥̅# ∧ 𝑥̅#∨𝑥$ ∧ 𝑥̅”∨𝑥̅#
22
𝜑= 𝑥̅”∨𝑥# ∧ 𝑥”∨𝑥# ∧ 𝑥̅”∨𝑥$ ∧ 𝑥#∨𝑥̅$ ∧ 𝑥̅#∨𝑥̅$ ∧ 𝑥”∨𝑥̅# ∧ 𝑥̅#∨𝑥$ ∧ 𝑥̅”∨𝑥̅#
TTTTFT
Computing𝐸 𝑊 𝜏 𝑥”=𝐹,𝑥# =𝐹 : Set 𝑥# to𝐹 𝐸 𝑊 𝜏 𝑥”=𝐹,𝑥# =𝐹 =6.5 1 + 0 + 1 + 1 + 1 + 1 + 1 + 1=6.5
𝜑=𝑥̅∨𝑥 ∧𝑥∨𝑥 ∧𝑥̅∨𝑥 ∧𝑥∨𝑥̅ ∧𝑥̅∨𝑥̅ ∧𝑥∨𝑥̅ ∧𝑥̅∨𝑥 ∧𝑥̅∨𝑥̅ “#”#”$#2$#$”##$”#
𝜑= 𝑥̅”∨𝑥# ∧ 𝑥”∨𝑥# ∧ 𝑥̅”∨𝑥$ ∧ 𝑥#∨𝑥̅$ ∧ 𝑥̅#∨𝑥̅$ ∧ 𝑥”∨𝑥̅# ∧ 𝑥̅#∨𝑥$ ∧ 𝑥̅”∨𝑥̅# TFT TTTT
Since𝐸 𝑊 𝜏 𝑥”=𝐹,𝑥# =𝐹 >𝐸 𝑊 𝜏 𝑥”=𝐹,𝑥# =𝑇
• we deterministically chose 𝑥# to be 𝐹, that is, we set 𝜏(𝑥#) = 𝐹
• and then continue to “derandomize the choice of 𝑥’’’
2021-04-07 CSC373 Winter 2021 – Sam Toueg 35
Derandomized Exact Max-𝑘-SAT approximation algorithm – An example The formula 𝜑 after setting 𝑥” to 𝐹 and 𝑥# to 𝐹 :
TFT TTTT
𝜑= 𝑥̅”∨𝑥# ∧ 𝑥”∨𝑥# ∧ 𝑥̅”∨𝑥$ ∧ 𝑥#∨𝑥̅$ ∧ 𝑥̅#∨𝑥̅$ ∧ 𝑥”∨𝑥̅# ∧ 𝑥̅#∨𝑥$ ∧ 𝑥̅”∨𝑥̅#
Computing𝐸 𝑊 𝜏 𝑥”=𝐹,𝑥# =𝐹,𝑥’ =𝑇 : 1+0+1+0+1+1+1+16
=6
𝜑= 𝑥̅”∨𝑥# ∧ 𝑥”∨𝑥# ∧ 𝑥̅”∨𝑥$ ∧ 𝑥#∨𝑥̅$ ∧ 𝑥̅#∨𝑥̅$ ∧ 𝑥”∨𝑥̅# ∧ 𝑥̅#∨𝑥$ ∧ 𝑥̅”∨𝑥=̅#
𝜑= 𝑥̅”∨𝑥# ∧ 𝑥”∨𝑥# ∧ 𝑥̅”∨𝑥$ ∧ 𝑥#∨𝑥̅$ ∧ 𝑥̅#∨𝑥̅$ ∧ 𝑥”∨𝑥̅# ∧ 𝑥̅#∨𝑥$ ∧ 𝑥̅”∨𝑥̅# TFTFTTTT
Computing𝐸 𝑊 𝜏 𝑥”=𝐹,𝑥# =𝐹,𝑥’ =𝐹 : =7 1+0+1+1+1+1+1+17
𝜑= 𝑥̅”∨𝑥# ∧ 𝑥”∨𝑥# ∧ 𝑥̅”∨𝑥$ ∧ 𝑥#∨𝑥̅$ ∧ 𝑥̅#∨𝑥̅$ ∧ 𝑥”∨𝑥̅# ∧ 𝑥̅#∨𝑥$ ∧ 𝑥̅”∨𝑥=̅# 𝜑= 𝑥̅”∨𝑥# ∧ 𝑥”∨𝑥# ∧ 𝑥̅”∨𝑥$ ∧ 𝑥#∨𝑥̅$ ∧ 𝑥̅#∨𝑥̅$ ∧ 𝑥”∨𝑥̅# ∧ 𝑥̅#∨𝑥$ ∧ 𝑥̅”∨𝑥̅#
TFTTTTTT
• Since𝐸 𝑊 𝜏 𝑥”=𝐹,𝑥# =𝐹,𝑥’ =𝐹 >𝐸 𝑊 𝜏 𝑥”=𝐹,𝑥# =𝐹,𝑥’ =𝑇 Ø we deterministically chose 𝑥’ to be 𝐹, that is, we set 𝜏(𝑥’) = 𝐹
• So the derandomized algorithm selected the following truth assignment:
Ø 𝜏: 𝑥”= 𝐹,𝑥# = 𝐹,𝑥’ = 𝐹 (which satisfies 7 clauses out of 8 here, not bad 🙂
2021-04-07 CSC373 Winter 2021 – Sam Toueg 36
Max-SAT
• Simple derandomized algorithm for Max-𝑘-SAT Ø”!’! −approximation
“!
• This gives:
ØMax-2-SAT⇒%⁄ =0.75ofOPT
&
o The best known approximation is 0.9401
ØMax-3-SAT⇒S⁄ ofOPT T
o [Håstad]: This is the best possible assuming P ≠ NP
2C0SC213-7034W-07inter 2021 – Sam Toueg CSC373 Winter 2021 37
End of CSC373 lectures! Thanks!
2021-04-07 CSC373 Winter 2021 – Sam Toueg 38