Approximation Algorithms
2021-04-05 CSC373 Winter 2021 – Sam Toueg 1
We saw approximation algorithms for:
• Δ-TSP [using MST]
• Minimum Vertex cover [greedy algorithm]
• Minimum Weighted Vertex Cover [ILP rounding]
• Makespan (on-line and off-line) [greedy algorithm] Approximation algorithms based on Local Search
• Max-Cut
• Exact Max-“-SAT (today)
2021-04-05 CSC373 Winter 2021 – Sam Toueg 2
Local Search Algorithms Exact Max-0-SAT
2021-04-05 CSC373 Winter 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 * maximizing the number (or total weight) of clauses satisfied under *
• Fact: Max-2-SAT is NP-hard (we will not prove this) 2021-04-05 CSC373 Winter 2021 – Sam Toueg 5
Exact Max-)-SAT
• Problem
Ø Input: An !-CNF formula ” = $! ∧ $” ∧ ⋯ ∧ $# each clause $$ has exactly ! literals
each clause $$ has a weight ‘$ ≥ 0
Ø Output: A truth assignment * maximizing the number (or total weight) of clauses satisfied under *
2021-04-05 CSC373 Winter 2021 – Sam Toueg 7
Exact Max-)-SAT
• Local Search Algorithm
Ø Initialize truth assignment * to the variables +% of ” arbitrarily
Ø While ∃ *’ in the local neighborhood of * such that *’ increases the number (or total weight) of clauses that are satisfied
oReplace * with *’
• Local neighborhood of #:
Ø-&(*) = set of all truth assignments obtained
by changing the value of at most 0 variables in *
Ø For 0 = 1 this consists of all the truth assignments obtained
by changing the value of * +% for one variable +% of ”
2021-04-05 CSC373 Winter 2021 – Sam Toueg 8
Exact Max-2-SAT
• Theorem: The local search algorithm with $ = 1 gives
a!⁄ approximationtoExactMax-2-SAT ”
• Proof:
Ø Let * be a local optimum found by the local search algorithm
Ø * partitions the set 5 of all the clauses of ” into: o #! = {clauses not satisfied under $}
o #” = {clauses where exactly one literal is true under $}
o ## = {clauses where both literals are true under $}
o Let % #! , % #” , % ## be the corresponding total weights
ØSo * achieves weight 6 5! + 6 5″
Ø Optimal solution *∗ achieves at most 6 5( + 6 5! + 6 5″ Ø We must show that:
ØClaim:65 +65 ≥”⁄⋅65 +65 +65 !”)(!”
Equivalently: 65 ≤!⁄⋅65 +65 +65 ()(!”
2021-04-05 CSC373 Winter 2021 – Sam Toueg 9
Example:
$ = ‘̅̅̅̅! ∨ ‘” ∧ ‘! ∨ ‘” ∧ ‘̅̅̅̅! ∨ ‘# ∧ ‘” ∨ ‘̅̅̅̅# ∧ ‘̅̅̅̅” ∨ ‘̅̅̅̅# ∧ ‘! ∨ ‘̅̅̅̅” ∧ ‘̅̅̅̅” ∨ ‘# ∧ ‘̅̅̅̅! ∨ ‘̅̅̅̅” ∧ ‘! ∨ ‘# , = local optimum? Yes!
u n d e r ,
*! : clauses of +
not satisfied under ,
*” : clauses of + where exactly one literal is true under ,
/
,
*!
*”
-” -# -$
./
.
./
B e c o m e T r u e Become False
-̅” ∨ -#
-# ∨ -̅$
2021-04-05
CSC373 Winter 2021 – Sam Toueg
10
*# :clausesof+ are true under ,
– ∨-̅ ” #
-̅ ∨- # $
7 clauses areTrue under ,
-” ∨ -#
-̅” ∨ -$
where both literals *#
-” ∨ -$
assume all weights are 1
-̅” ∨ -̅# -̅# ∨ -̅$
$ =
*!
*” *#
‘̅̅̅̅ !
–
‘̅̅̅̅ ∨ ‘ ! #
∧
‘ ∨ ‘̅̅̅̅ ∧ ” #
-”
‘̅̅̅̅ ∨ ‘̅̅̅̅ ” #
∧
‘ ∨ ‘̅̅̅̅ ! ”
∧ ‘̅̅̅̅ ”
-#
∨ ‘ #
∧
‘̅̅̅̅ !
∨ ‘̅̅̅̅ ”
∧ ‘ !
-$
∨ ‘ #
∨ ‘ ” ”
∧ ‘ ∨ ‘ ∧
! under ,
”
-̅” ∨-# -” ∨-#
-̅” ∨-$
-# ∨-̅$ -̅” ∨-̅#
-̅# ∨-̅$
-̅” ∨-#
3″ 3# 3$
2″ -̅” ∨-#
2#
-# ∨-̅$
2$ -# ∨ -̅$
-” ∨-#
-̅” ∨-̅#
-̅# ∨-̅$
-̅” ∨-$
ØAclauseinvolvesvariable4ifitcontains- or-5 %%
• 2% = { clauses in *! involving variable 4 }
• 3% = { clauses in *” that are True because the literal of variable 4 is true under ,} Ø Let 6 2% , 6 3% be the corresponding total weights
2021-04-05 CSC373 Winter 2021 – Sam Toueg 11
$ =
*!
*” *#
‘̅̅̅̅ !
–
‘̅̅̅̅ ∨ ‘ ! #
∧
‘ ∨ ‘̅̅̅̅ ∧ ” #
-”
‘̅̅̅̅ ∨ ‘̅̅̅̅ ” #
∧
‘ ∨ ‘̅̅̅̅ ! ”
∧ ‘̅̅̅̅ ”
-#
∨ ‘ #
∧
‘̅̅̅̅ !
∨ ‘̅̅̅̅ ”
∧ ‘ !
-$
∨ ‘ #
∨ ‘ ” ”
∧ ‘ ∨ ‘ ∧
! under ,
”
-̅” ∨-# -” ∨-#
-̅” ∨-$
-# ∨-̅$ -̅” ∨-̅#
-̅# ∨-̅$
-̅” ∨-#
3″ 3# 3$
2″ -̅” ∨-#
2#
-# ∨-̅$
2$ -# ∨ -̅$
-” ∨-#
-̅” ∨-̅#
-̅# ∨-̅$
-̅” ∨-$
Ø Each clause in *! involves two variables, so
Ø Each clause in *! appears exactly twice in 2″ , 2# , …, 2& (8: number of variables in +).
Ø So the total weight of the clauses in *! is half the total weights of the clauses in 2″ , 2# , …, 2&
Ø In other words:
Lemma1:26 *! =∑%6 2%
Inourexample:26 *! =6 2″ +6 2# +6 2$
2021-04-05 CSC373 Winter 2021 – Sam Toueg 12
$ =
*!
*” *#
‘̅̅̅̅ !
–
‘̅̅̅̅ ∨ ‘ ! #
∧
‘ ∨ ‘̅̅̅̅ ∧ ” #
-”
‘̅̅̅̅ ∨ ‘̅̅̅̅ ” #
∧
‘ ∨ ‘̅̅̅̅ ! ”
∧ ‘̅̅̅̅ ”
-#
∨ ‘ #
∧
‘̅̅̅̅ !
∨ ‘̅̅̅̅ ”
∧ ‘ !
-$
∨ ‘ #
∨ ‘ ” ”
∧ ‘ ∨ ‘ ∧
! under ,
”
-̅” ∨-# -” ∨-#
-̅” ∨-$
-# ∨-̅$ -̅” ∨-̅#
-̅# ∨-̅$
-̅” ∨-#
3″ 3# 3$
-” ∨-# -̅” ∨-̅# -̅# ∨-̅$ -̅” ∨-$
2″ -̅” ∨-#
2#
-# ∨-̅$
2$ -# ∨ -̅$
Ø *” is the set of clauses that are True “because’’ of exactly one variable (under ,) Ø 3% is the set of clauses of *” that are True (under ,) “because’’ of variable 4
Ø Thus, *” = ⋃% 3%
Ø Therefore:
Lemma2:6 *” =∑%6 3%
2021-04-05 CSC373 Winter 2021 – Sam Toueg 13
$ =
*!
*” *#
‘̅̅̅̅ !
–
‘̅̅̅̅ ∨ ‘ ! #
∧
‘ ∨ ‘̅̅̅̅ ∧ ” #
-”
‘̅̅̅̅ ∨ ‘̅̅̅̅ ” #
∧
‘ ∨ ‘̅̅̅̅ ! ”
∧ ‘̅̅̅̅ ”
-#
∨ ‘ #
∧
‘̅̅̅̅ !
∨ ‘̅̅̅̅ ”
∧ ‘ !
-$
∨ ‘ #
∨ ‘ ” ”
∧ ‘ ∨ ‘ ∧
! under ,
”
-̅” ∨-# -” ∨-#
-# ∨-̅$ -̅” ∨-̅#
-̅” ∨-#
3″ 3# 3$
2″ -̅” ∨-#
2#
-# ∨-̅$
2$ -# ∨ -̅$
-” ∨-# -̅” ∨-̅# -̅# ∨-̅$ -̅” ∨-$ Ø If we flip the truth assignment ,(-%) of a variable -%:
Ø All the clauses in 2% become True (because they involve -% but are False under , )
Ø All the clauses in 3% become False (because they were True only because of , -% )
-̅” ∨-$
-̅# ∨-̅$
Ø The other clauses in *! ∪ *” ∪ *# do not change truth value (do you see why?) Ø Thus, if we flip ,(-%) the net change in total weight is: 6 2% − 6 3%
Ø Since the , that we consider is a local optimum, this net change can not be positive! Ø So: 6 2% − 6 3% ≤ 0 that is: 6 2% ≤ 6 3%
ØBysummingoverall4: Lemma3:∑ 6 2 ≤∑ 6 3
2021-04-05 % % % % 14
• Theorem: The local search with $ = 1 gives a
!⁄ approximationtoExactMax-2-SAT
• Proof: We showed ØLemma1:265( =∑%6H% ØLemma2:65! =∑%6I% ØLemma3:∑%6H% ≤∑%6I%
”
ØBy chaining the above: 2 6 5( Ø By adding 6 5( to both sides:
≤ 6 5!
o3%#! ≤%#! +%#” ≤%#! +%#” +%##
o%# ≤”⁄⋅%# +%# +%# !*!”#
o Precisely the condition we wanted to prove! Q.E.D.
2021-04-05 CSC373 Winter 2021 – Sam Toueg 15
Exact Max-2-SAT
• Better approximation?
Ø We can learn something from our approximation proof:
Ø We did not use anything about 6 5″ ! We simply added it attheendofinequality36 5( ≤6 5( +6 5!
ØIf we could also guarantee that 6 5( ≤ 6 5″ … oThenwewouldget4% #! ≤% #! +% #” +% ## ,
whichwouldgivea*⁄ approximation +
Ø It can be shown that this can be done by including just one more assignment to the neighborhood -! * :
– * =-! * ∪ *J ,where*J =complementof*
i.e., *J is obtained from * by flipping all its truth assignments
• Result (we will not prove this):
Ø Neighborhood – * ∪ *J ⇒ )⁄ -apx for Exact Max-2-SAT
!K
2021-04-05 CSC373 Winter 2021 – Sam Toueg 17
Exact Max-2-SAT
• What if we do not want to modify the -! * neighborhood?
• A different tweak also works…
• Intuition: note that 5″ clauses are more “robust’’ than those in 5! because they remain true under single variable changes
(with a single variable change, clauses in 5! may become false).
• So we could try to give more importance to creating 5″ clauses
• So far: the objective function was to increase 6 5! + 6 5″
(the total weight of clauses that are satisfied)
• A modified objective function is to increase 1.5 6 5! + 2 6(5″)
• This gives more weight to increasing 6 5″ , but does it work?
2021-04-05 CSC373 Winter 2021 – Sam Toueg 18
Exact Max-2-SAT
• Modified local search:
Ø Start at arbitrary truth assignment *
ØWhile∃*L ∈-! * thatincreases1.56 5! +26 5″ o Switch to $,
• Result (we will not prove this):
Ø This gives a )⁄ -approximation to Exact Max-2-SAT. K
2021-04-05
CSC373 Winter 2021 – Sam Toueg 20
Exact Max-2-SAT – Summary -!(*) = set of all truth assignments obtained
by changing the value of at most one variables in * • Result 1 (proved here):
Ø Neighborhood – (*) ⇒ “⁄ -apx for Exact Max-2-SAT !)
• Result 2 (not shown):
Ø Neighborhood – * ∪ *J ⇒ )⁄ -apx for Exact Max-2-SAT
!K
• Result 3 (not shown):
Ø Neighborhood -! * + modified objective function ⇒
)⁄ -apx for Exact Max-2-SAT K
2C0SC213-7034W-05inter 2021 – Sam Toueg CSC373 Winter 2020 21
Exact Max-)-SAT
• More generally (” ≥ 2):
Ø This modified local search works for higher values of !:
Ø It gives “!M! approximation for Exact Max-!-SAT “!
Ø But we will soon see how to achieve this same result using a simpler technique!
• For ! = 3, this is a N⁄ approximation for Exact Max-3-SAT O
• Theorem [Håstad]: Achieving N⁄ + R approximation O
for any R > 0 is NP-hard!
2021-04-05 CSC373 Winter 2021 – Sam Toueg 22