CSC373
Weeks 9 & 10: Approximation Algorithms & Local Search
373F20 – Nisarg Shah 1
NP-Completeness
• NP-complete problems
➢ Unlikely to have polynomial time algorithms to solve them ➢ What do we do?
• One idea: approximation
➢ Instead of solving them exactly, solve them approximately
➢ Sometimes, we might want to use an approximation algorithm even when we can compute an exact solution in polynomial time (WHY?)
373F20 – Nisarg Shah 2
Approximation Algorithms
• Decision versus optimization problems
➢ Decision variant: “Does there exist a solution with objective ≥ 𝑘?”
o E.g. “Is there an assignment which satisfies at least 𝑘 clauses of a given CNF formula 𝜑?”
➢ Optimization variant: “Find a solution maximizing objective”
o E.g. “Find an assignment which satisfies the maximum possible
number of clauses of a given CNF formula 𝜑.”
➢ If a decision problem is hard, then its optimization version is hard too ➢ We’ll focus on optimization variants
373F20 – Nisarg Shah 3
Approximation Algorithms
• Objectives
➢ Maximize (e.g. “profit”) or minimize (e.g. “cost”)
• Given problem instance 𝐼:
➢ 𝐴𝐿𝐺(𝐼) = solution returned by our algorithm ➢ 𝑂𝑃𝑇(𝐼) = some optimal solution
➢ Approximation ratio of 𝐴𝐿𝐺 on instance 𝐼 is 𝑝𝑟𝑜𝑓𝑖𝑡 𝑂𝑃𝑇 𝐼 or 𝑐𝑜𝑠𝑡 𝐴𝐿𝐺 𝐼
𝑝𝑟𝑜𝑓𝑖𝑡 𝐴𝐿𝐺 𝐼 𝑐𝑜𝑠𝑡 𝑂𝑃𝑇 𝐼
➢ Convention: approximation ratio ≥ 1
o “2-approximation” = half the optimal profit / twice the optimal cost
373F20 – Nisarg Shah 4
Approximation Algorithms
• Worst-case approximation ratio
➢ Worst approximation ratio across all possible problem instances 𝐼
➢ 𝐴𝐿𝐺 has worst-case 𝑐-approximation if for each problem instance 𝐼… 𝑝𝑟𝑜𝑓𝑖𝑡 𝐴𝐿𝐺 𝐼 ≥1⋅𝑝𝑟𝑜𝑓𝑖𝑡 𝑂𝑃𝑇 𝐼 𝑜𝑟
𝑐
𝑐𝑜𝑠𝑡 𝐴𝐿𝐺 𝐼 ≤𝑐⋅𝑐𝑜𝑠𝑡 𝑂𝑃𝑇 𝐼
➢ By default, we will always refer to approximation ratios in the worst case
➢ Note: In some textbooks, you might see the approximation ratio flipped (e.g. 0.5-approximation instead of 2-approximation)
373F20 – Nisarg Shah 5
PTAS and FPTAS
• Arbitrarily close to 1 approximations
• PTAS: Polynomial time approximation scheme
➢ For every 𝜖 > 0, there is a 1 + 𝜖 -approximation algorithm that
runs in time 𝑝𝑜𝑙𝑦 𝑛 on instances of size 𝑛
o Note: Could have exponential dependence on 1Τ𝜖
• FPTAS: Fully polynomial time approximation scheme
➢ For every 𝜖 > 0, there is a 1 + 𝜖 -approximation algorithm that runs in time 𝑝𝑜𝑙𝑦 𝑛, 1Τ𝜖 on instances of size 𝑛
373F20 – Nisarg Shah 6
Approximation Landscape
➢ An FPTAS
o E.g. the knapsack problem
➢ A PTAS but no FPTAS
o E.g. the makespan problem (we’ll see)
Impossibility of better approximations assuming widely held beliefs like P ≠ NP
𝑛 = parameter of problem at hand
➢ 𝑐-approximation for a constant 𝑐 > 1 but no PTAS o E.g. vertex cover and JISP (we’ll see)
➢ Θ log 𝑛 -approximation but no constant approximation o E.g. set cover
➢ No 𝑛1−𝜖-approximation for any 𝜖 > 0
o E.g. graph coloring and maximum independent set
373F20 – Nisarg Shah 7
Approximation Techniques
• Greedy algorithms
➢ Make decision on one element at a time in a greedy fashion without
considering future decisions
• LP relaxation
➢ Formulate the problem as an integer linear program (ILP)
➢ “Relax” it to an LP by allowing variables to take real values
➢ Find an optimal solution of the LP, “round” it to a feasible solution of the original ILP, and prove its approximate optimality
• Local search
➢ Start with an arbitrary solution
➢ Keep making “local” adjustments to improve the objective
373F20 – Nisarg Shah 8
Greedy Approximation
373F20 – Nisarg Shah 9
Makespan Minimization
373F20 – Nisarg Shah 10
Makespan
• Problem
➢ Input: 𝑚 identical machines, 𝑛 jobs, job 𝑗 requires processing time 𝑡
➢ Output: Assign jobs to machines to minimize makespan ➢ Let 𝑆 𝑖 = set of jobs assigned to machine 𝑖 in a solution
➢ Constraints:
o Each job must run contiguously on one machine
o Each machine can process at most one job at a time
➢Loadonmachine𝑖:𝐿 =σ 𝑡 𝑖 𝑗∈𝑆𝑖𝑗
➢ Goal: minimize the maximum load, i.e., makespan 𝐿 = max 𝐿𝑖 𝑖
𝑗
373F20 – Nisarg Shah 11
Makespan
• Even the special case of 𝑚 = 2 machines is already NP-hard by
reduction from PARTITION
• PARTITION
➢ Input: Set 𝑆 containing 𝑛 integers
➢ Question: Does there exist a partition of 𝑆 into two sets with equal sum? (Apartitionof𝑆into𝑆 ,𝑆 means𝑆 ∩𝑆 =∅and𝑆 ∪𝑆 =𝑆)
• Exercise!
➢ Show that PARTITION is NP-complete by reduction from SUBSET-SUM
➢ Show that Makespan with 𝑚 = 2 is NP-complete by reduction from PARTITION
121212
373F20 – Nisarg Shah 12
Makespan
• Greedy list-scheduling algorithm
➢ Consider the 𝑛 jobs in some “nice” sorted order
➢ Assign each job 𝑗 to a machine with the smallest load so far
• Note: Implementable in 𝑂 𝑛 log 𝑚 using priority queue
• Back to greedy…?
➢ But this time, we can’t hope that greedy will be optimal ➢ We can still hope that it is approximately optimal
• Which order?
373F20 – Nisarg Shah 13
Makespan
• Theorem [Graham 1966]
➢ Regardless of the order, greedy gives a 2-approximation.
➢ This was one of the first worst-case approximation analyses
∗ • Let optimal makespan = 𝐿
• To show that makespan under the greedy solution is not much
∗∗
worse than 𝐿 , we need to show that 𝐿 cannot be too low
373F20 – Nisarg Shah 14
Makespan
• Theorem [Graham 1966]
➢ Regardless of the order, greedy gives a 2-approximation.
∗
• Fact1:𝐿 ≥max𝑡
𝑗
➢ Some machine must process job with highest processing time
1 •Fact2:𝐿≥ σ𝑡
∗
𝑗𝑗
𝑗
𝑚
➢ Total processing time is σ 𝑡 𝑗𝑗
➢ At least one machine must do at least 1/𝑚 of this work (the pigeonhole principle)
373F20 – Nisarg Shah 15
Makespan
• Theorem [Graham 1966]
➢ Regardless of the order, greedy gives a 2-approximation.
• Proof:
➢ Suppose machine 𝑖 is the bottleneck under greedy (so 𝐿 = 𝐿𝑖)
➢ Let 𝑗∗ be the last job scheduled on machine 𝑖 by greedy ➢ Right before 𝑗∗ was assigned to 𝑖, 𝑖 had the smallest load
o Load of the other machines could have only increased from then o𝐿 −𝑡∗ ≤𝐿 ,∀𝑘
𝑖𝑗𝑘
➢ Average over all 𝑘 : 𝐿 − 𝑡 ∗ ≤ 1 σ 𝑡 𝑖𝑗𝑚𝑗𝑗
Fact1 Fact 2
∗ 1σ ∗ ∗ ∗
➢𝐿 ≤𝑡 + 𝑡 ≤𝐿 +𝐿 =2𝐿 𝑖𝑗𝑚𝑗𝑗
373F20 – Nisarg Shah 16
Makespan
• Theorem [Graham 1966]
➢
• Is ➢ ➢
➢ ➢
Regardless of the order, greedy gives a 2-approximation.
our analysis tight?
Essentially.
By averaging over 𝑘 ≠ 𝑖 in the previous slide, one can show a slightly
better 2 − 1/𝑚 approximation
There is an example where greedy has approximation as bad as 2 − 1/𝑚 So 2 − 1/𝑚 is exactly tight.
373F20 – Nisarg Shah 17
Makespan
• Tight example:
➢ 𝑚(𝑚 − 1) jobs of length 1, followed by one job of length 𝑚
➢ Greedy evenly distributes unit length jobs on all 𝑚 machines, and assigning the last heavy job makes makespan 𝑚 − 1 + 𝑚 = 2𝑚 − 1
➢ Optimal makespan is 𝑚 by evenly distributing unit length jobs among 𝑚 − 1 machines and putting the single heavy job on the remaining
• Idea:
➢ It seems keeping heavy jobs at the end is bad. ➢ So let’s just start with them first!
373F20 – Nisarg Shah 18
Makespan Revisited
• Greedy LPT (Longest Processing Time First)
➢ Run the greedy algorithm but consider jobs in a non-increasing order
of their processing time ➢Suppose𝑡1 ≥𝑡2 ≥⋯≥𝑡𝑛
• Fact 3: If the bottleneck machine 𝑖 has only one job 𝑗, then the solution is optimal.
➢ Current solution has 𝐿 = 𝐿 = 𝑡 𝑖𝑗
∗
∗ • Fact 4: If there are more than 𝑚 jobs, then 𝐿
➢ We know 𝐿 ≥ 𝑡 from Fact 1 𝑗
➢ The first 𝑚 + 1 jobs each have processing time at least 𝑡𝑚+1
➢ By the pigeonhole principle, the optimal solution must put at least two of them on the same machine
≥ 2 ⋅ 𝑡𝑚+1
373F20 – Nisarg Shah 19
Makespan Revisited
• Theorem
➢ Greedy LPT achieves 3/2-approximation
• Proof:
➢ Similar to the proof for arbitrary ordering
➢ Consider a bottleneck machine 𝑖 and the job 𝑗∗ that was last scheduled on this machine by the greedy algorithm
➢ Case 1: Machine 𝑖 has only one job 𝑗∗
o By Fact 3, greedy is optimal in this case (i.e. 1-approximation)
373F20 – Nisarg Shah 20
Makespan Revisited
• Theorem
➢ Greedy LPT achieves 3/2-approximation
• Proof:
➢ Similar to the proof for arbitrary ordering
➢ Consider a bottleneck machine 𝑖 and the job 𝑗∗ that was last scheduled on this machine by the greedy algorithm
➢ Case 2: Machine 𝑖 has at least two jobs oJob𝑗∗ musthave𝑡∗ ≤𝑡
o As before, 𝐿 = 𝐿 Same as before
= 𝐿 − 𝑡 ∗ + 𝑡 ∗ 𝑖𝑖𝑗𝑗
∗ ≤ 1.5 𝐿
𝑗 𝑚+1
∗ ∗
≤ 𝐿 ≤ 𝐿 /2
𝑡 ∗ 𝑗
≤ 𝑡 𝑚+1
and Fact 4
373F20 – Nisarg Shah 21
Makespan Revisited
• Theorem
➢ Greedy LPT achieves 3/2-approximation ➢ Is our analysis tight? No!
• Theorem [Graham 1966]
➢ Greedy LPT achieves 4 − 1 -approximation
3 3m
➢ Is Graham’s approximation tight? oYes.
o In the upcoming example, greedy LPT is as bad as 4 − 1 3 3𝑚
373F20 – Nisarg Shah 22
Makespan Revisited
• Tight example for Greedy LPT:
➢ 2 jobs each of lengths 𝑚,𝑚 + 1,…,2𝑚 − 1
➢ One more job of length 𝑚
➢ Greedy-LPT has makespan 4𝑚 − 1 (verify!) ➢ OPT has makespan 3𝑚 (verify!)
➢ Thus, approximation ratio is at least as bad as 4𝑚−1 = 4 − 1 3𝑚 3 3𝑚
373F20 – Nisarg Shah 23
Weighted Set Packing
373F20 – Nisarg Shah 24
Weighted Set Packing
• Problem
➢ Input: Universe of 𝑚 elements, sets 𝑆 ,…,𝑆 with values 𝑣 ,…,𝑣 ≥ 0
➢ Output: Pick disjoint sets with maximum total value
o That is, pick 𝑊 ⊆ {1, … , 𝑛} to maximize σ𝑖∈𝑊 𝑣𝑖 subject to
𝑆 ∩𝑆 =∅forall𝑖,𝑗∈𝑊 𝑖𝑗
➢ What’s known about this problem? o It’s NP-hard
1
o For any constant ε > 0, you cannot get O m Τ −ε
1𝑛 1𝑛
approximation in polynomial time unless NP=ZPP (widely believed to be not true)
2
373F20 – Nisarg Shah 25
Greedy Template
• Sort the sets in some order, consider them one-by-one, and take any set that you can along the way.
• Greedy Algorithm:
➢ Sort the sets in a specific order.
➢ Relabel them as 1,2, … , 𝑛 in this order. ➢𝑊←∅
➢ For 𝑖 = 1, … , 𝑛:
o If 𝑆 ∩ 𝑆 = ∅ for every 𝑗 ∈ 𝑊, then 𝑊 ← 𝑊 ∪ {𝑖} 𝑖𝑗
➢ Return 𝑊.
373F20 – Nisarg Shah 26
Greedy Algorithm
• What order should we sort the sets by? • We want to take sets with high values.
➢ 𝑣 ≥ 𝑣 ≥ ⋯ ≥ 𝑣 ? Only 𝑚-approximation 12𝑛
• We don’t want to exhaust many items too soon. ➢ 𝑣1 ≥ 𝑣2 ≥ ⋯ 𝑣𝑛 ? Also 𝑚-approximation
• 𝑚-approximation : 𝑣1 ≥ 𝑣2 ≥ ⋯ 𝑣𝑛 ? 𝑆1 𝑆2 𝑆𝑛
[Lehmann et al. 2011]
𝑆1 𝑆2 𝑆𝑛
373F20 – Nisarg Shah 27
Proof of Approximation
• Definitions
➢ 𝑂𝑃𝑇 = Some optimal solution
➢ 𝑊 = Solution returned by our greedy algorithm
➢For𝑖∈𝑊,𝑂𝑃𝑇 = 𝑗∈𝑂𝑃𝑇∶ 𝑗≥𝑖, 𝑆 ∩𝑆 ≠∅ 𝑗𝑖𝑖
𝑇𝑃𝑂 ڂ⊆𝑇𝑃𝑂:Claim1 • 𝑖 𝑊∈𝑖
• Claim 2: It is enough to show that ∀𝑖 ∈ 𝑊 𝑚⋅𝑣≥Σ 𝑣
𝑗 𝑖𝑇𝑃𝑂∈𝑗 𝑖
• Observation:For𝑗∈𝑂𝑃𝑇,𝑣 ≤𝑣 ⋅ 𝑖𝑗𝑖
𝑗𝑆 𝑖𝑆
373F20 – Nisarg Shah 28

Proof of Approximation
• Summing over all 𝑗 ∈ 𝑂𝑃𝑇 : 𝑖
Σ 𝑣≤𝑣𝑖⋅Σ 𝑆 𝑗∈𝑂𝑃𝑇𝑖 𝑗 𝑆 𝑗∈𝑂𝑃𝑇𝑖 𝑗
𝑖
• Using Cauchy-Schwarz (Σ𝑖 𝑥𝑖𝑦𝑖 ≤ Σ𝑖 𝑥2 ⋅ 𝑖𝑖
Σ𝑖 𝑦2) Σ 1.𝑆≤𝑂𝑃𝑇⋅Σ 𝑆
𝑗∈𝑂𝑃𝑇𝑖𝑗 𝑖𝑗∈𝑂𝑃𝑇𝑖𝑗
≤𝑆⋅𝑚 𝑖
373F20 – Nisarg Shah 29
Unweighted Vertex Cover
373F20 – Nisarg Shah 30
Unweighted Vertex Cover
• Problem
➢ Input: Undirected graph 𝐺 = (𝑉, 𝐸)
➢ Output: Vertex cover 𝑆 of minimum cardinality
➢ Recall: 𝑆 is vertex cover if every edge has at least one of its two endpoints in 𝑆
➢ We already saw that this problem is NP-hard
• Q: What would be a good greedy algorithm for this problem?
373F20 – Nisarg Shah 31
Unweighted Vertex Cover
• Greedy edge-selection algorithm:
➢ Start with 𝑆 = ∅
➢ While there exists an edge whose both endpoints are not in 𝑆, add both its endpoints to 𝑆
• Hmm…
➢ Why are we selecting edges rather than vertices?
➢ Why are we adding both endpoints? ➢ We’ll see..
373F20 – Nisarg Shah 32
Unweighted Vertex Cover
373F20 – Nisarg Shah 33
Unweighted Vertex Cover
• Theorem:
➢ Greedy edge-selection algorithm for unweighted vertex cover
achieves 2-approximation.
• Observation 1:
➢ For any vertex cover 𝑆∗ and any matching 𝑀, 𝑆∗ ≥ 𝑀 , where
𝑀 = number of edges in 𝑀
➢ Proof: 𝑆∗ must contain at least one endpoint of each edge in 𝑀
• Observation 2:
➢ Greedy algorithm finds a vertex cover of size 𝑆 = 2 ⋅ 𝑀
• Hence, 𝑆 ≤ 2 ⋅ 𝑆∗ , where 𝑆∗ = min vertex cover
373F20 – Nisarg Shah 34
Unweighted Vertex Cover
• Corollary:
➢ If 𝑀∗ is a maximum matching, and 𝑀 is a maximal matching, then
𝑀 ≥1 𝑀∗
2
• Proof:
➢Bydesign, 𝑀 =1|𝑆|
2
➢ 𝑆 ≥ 𝑀∗ (Observation 1)
➢Hence, 𝑀 ≥1 𝑀∗ ∎ 2
• This greedy algorithm is also a 2-approximation to the problem of finding a maximum cardinality matching
➢ However, the max cardinality matching problem can be solved exactly in polynomial time using a more complex algorithm
373F20 – Nisarg Shah 35
Unweighted Vertex Cover
• What about a greedy vertex selection algorithm? ➢ Start with 𝑆 = ∅
➢ While 𝑆 is not a vertex cover:
o Choose a vertex 𝑣 which maximizes the number of uncovered edges incident on it
o Add 𝑣 to 𝑆
➢ Gives 𝑂 log 𝑑max approximation, where 𝑑max is the maximum
degree of any vertex
o But unlike the edge-selection version, this generalizes to set cover
o For set cover, 𝑂 log 𝑑max approximation ratio is the best possible in polynomial time unless P=NP
373F20 – Nisarg Shah 36
Unweighted Vertex Cover
• Theorem [Dinur-Safra 2004]:
NOT IN SYLLABUS
➢ Unless P = NP, there is no polynomial-time 𝜌-approximation algorithm for unweighted vertex cover for any constant 𝜌 < 1.3606.
373F20 - Nisarg Shah 37
Unweighted Vertex Cover
• Theorem [Khot-Regev 2008]:
NOT IN SYLLABUS
➢ Unless the “unique games conjecture” is violated, there is no polynomial-time 𝜌-approximation algorithm for unweighted vertex cover for any constant 𝜌 < 2.
373F20 - Nisarg Shah 38
Unweighted Vertex Cover
NOT IN SYLLABUS
• How does one prove a lower bound on the approximation ratio of any polynomial-time algorithm?
➢ We prove that if there is a polynomial-time 𝜌-approximation algorithm for the problem with 𝜌 < some bound, then some widely believed conjecture is violated
➢ For example, we can prove that given a polynomial time 𝜌- approximation algorithm to vertex cover for any constant 𝜌 < 1.3606, we can use this algorithm as a subroutine to solve the 3SAT decision problem in polynomial time, implying P=NP
➢ Similar technique can be used to reduce from other widely believed conjectures, which may give different (sometimes better) bounds
➢ Beyond the scope of this course
373F20 - Nisarg Shah 39
Weighted Vertex Cover
373F20 - Nisarg Shah 40
Weighted Vertex Cover
• Problem
➢ Input: Undirected graph 𝐺 = (𝑉, 𝐸), weights 𝑤 ∶ 𝑉 → 𝑅≥0 ➢ Output: Vertex cover 𝑆 of minimum total weight
• The same greedy algorithm doesn’t work
➢ Gives arbitrarily bad approximation
➢ Obvious modifications which try to take weights into account also don’t work
➢ Need another strategy...
373F20 - Nisarg Shah 41
LP Relaxation
373F20 - Nisarg Shah 42
ILP Formulation
➢ For each vertex 𝑣, create a binary variable 𝑥𝑣 ∈ {0,1} indicating
whether vertex 𝑣 is chosen in the vertex cover
➢ Then, computing min weight vertex cover is equivalent to solving the
following integer linear program
minΣ 𝑤 ⋅𝑥 𝑣𝑣𝑣
subject to 𝑥𝑢+𝑥𝑣≥1, 𝑥𝑣 ∈ 0,1 ,
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
373F20 - Nisarg Shah 43
LP Relaxation
• What if we solve the “LP relaxation” of the original ILP? ➢ Just convert all integer variables to real variables
ILP with binary variables LP with real variables
minΣ 𝑤 ⋅𝑥 minΣ 𝑤 ⋅𝑥 𝑣𝑣𝑣 𝑣𝑣𝑣
subject to 𝑥𝑢+𝑥𝑣≥1, 𝑥𝑣 ∈ 0,1 ,
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
subject to
𝑥𝑢+𝑥𝑣≥1, ∀𝑢,𝑣 ∈𝐸 𝑥𝑣 ≥ 0, ∀𝑣 ∈ 𝑉
373F20 - Nisarg Shah 44
Rounding LP Solution
• What if we solve the “LP relaxation” of the original ILP? ➢ Let’s say we are minimizing objective 𝑐𝑇𝑥
➢ Since the LP minimizes this over a larger feasible space than the ILP, optimal LP objective value ≤ optimal ILP objective value
➢ Let 𝑥∗ be an optimal LP solution (which we can compute efficiently) and ∗ 𝐿𝑃
𝑥𝐼𝐿𝑃 be an optimal ILP solution (which we can’t compute efficiently) o𝑐𝑇𝑥∗ ≤𝑐𝑇𝑥∗
𝐿𝑃 𝐼𝐿𝑃
o But 𝑥∗ may have non-integer values 𝐿𝑃
o Efficiently round 𝑥∗ to an ILP feasible solution 𝑥ො without increasing 𝐿𝑃
the objective too much
o If we prove 𝑐𝑇 𝑥ො ≤ 𝜌 ⋅ 𝑐𝑇𝑥∗ , then we will also have 𝑐𝑇 𝑥ො ≤ 𝜌 ⋅ 𝑐𝑇𝑥∗
o Thus, our algorithm will achieve 𝜌-approximation
𝐿𝑃 𝐼𝐿𝑃
373F20 - Nisarg Shah 45
Rounding LP Solution
• What if we solve the “LP relaxation” of the original ILP?
➢ If we are maximizing 𝑐𝑇𝑥 instead of minimizing, then it’s reversed:
o Optimal LP objective value ≥ optimal ILP objective value, i.e., 𝑐𝑇𝑥∗ ≥ 𝑐𝑇𝑥∗
𝐿𝑃 𝐼𝐿𝑃
o Efficiently round 𝑥∗ to an ILP feasible solution 𝑥ො without decreasing 𝐿𝑃
the objective too much
𝑇1𝑇∗ 𝑇1𝑇∗
o If we prove 𝑐 𝑥ො ≥ Τ
𝜌 𝐿𝑃
⋅ 𝑐 𝑥 , then 𝑐 𝑥ො ≥ Τ
𝜌 𝐼𝐿𝑃
⋅ 𝑐 𝑥
o Thus, our algorithm will achieve 𝜌-approximation
373F20 - Nisarg Shah 46
Weighted Vertex Cover
• Consider LP optimal solution 𝑥∗
➢Let𝑥ො =1whenever𝑥∗ ≥0.5and𝑥ො =0otherwise
𝑣𝑣𝑣
➢ Claim 1: 𝑥ො is a feasible solution of ILP (i.e. a vertex cover)
oFor every edge 𝑢,𝑣 ∈ 𝐸, at least one of 𝑥∗,𝑥∗ is at least 0.5 𝑢𝑣
o So at least one of 𝑥ො𝑢, 𝑥ො𝑣 ILP with binary variables
is 1 ∎
LP with real variables
minΣ 𝑤 ⋅𝑥
𝑣𝑣𝑣 𝑣𝑣𝑣
subject to 𝑥𝑢+𝑥𝑣≥1, 𝑥𝑣 ∈ 0,1 ,
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
minΣ 𝑤 ⋅𝑥
subject to
𝑥𝑢+𝑥𝑣≥1, ∀𝑢,𝑣 ∈𝐸 𝑥𝑣 ≥ 0, ∀𝑣 ∈ 𝑉
373F20 - Nisarg Shah 47
Rounding LP Solution
• Consider LP optimal solution 𝑥∗
➢Let𝑥ො =1whenever𝑥∗ ≥0.5and𝑥ො =0otherwise
subject to 𝑥𝑢+𝑥𝑣≥1, 𝑥𝑣 ∈ 0,1 ,
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
subject to
𝑥𝑢+𝑥𝑣≥1, ∀𝑢,𝑣 ∈𝐸 𝑥𝑣 ≥ 0, ∀𝑣 ∈ 𝑉
𝑣𝑣𝑣
➢Claim2:σ 𝑤 ⋅𝑥ො ≤2∗σ 𝑤 ⋅𝑥∗ 𝑣𝑣𝑣 𝑣𝑣𝑣
o Weight only increases when some 𝑥∗ ∈ [0.5,1] is rounded up to 1 𝑣
o At most doubling the variable, so at least doubling the weight ∎ ILP with binary variables LP with real variables
minΣ 𝑤 ⋅𝑥 minΣ 𝑤 ⋅𝑥 𝑣𝑣𝑣 𝑣𝑣𝑣
373F20 - Nisarg Shah 48
Rounding LP Solution
• Consider LP optimal solution 𝑥∗
➢Let𝑥ො =1whenever𝑥∗ ≥0.5and𝑥ො =0otherwise
𝑣𝑣𝑣
➢ Hence, 𝑥ො is a vertex cover with weight at most 2 ∗ LP optimal value ≤ 2 ∗
ILP optimal value
ILP with binary variables LP with real variables
minΣ 𝑤 ⋅𝑥 minΣ 𝑤 ⋅𝑥 𝑣𝑣𝑣 𝑣𝑣𝑣
subject to 𝑥𝑢+𝑥𝑣≥1, 𝑥𝑣 ∈ 0,1 ,
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
subject to
𝑥𝑢+𝑥𝑣≥1, ∀𝑢,𝑣 ∈𝐸 𝑥𝑣 ≥ 0, ∀𝑣 ∈ 𝑉
373F20 - Nisarg Shah 49
General LP Relaxation Strategy
• Your NP-complete problem amounts to solving
➢ Max 𝑐𝑇𝑥 subject to 𝐴𝑥 ≤ 𝑏,𝑥 ∈ N (need not be binary)
• Instead, solve:
➢ Max 𝑐𝑇𝑥 subject to 𝐴𝑥 ≤ 𝑏, 𝑥 ∈ R≥0 (LP relaxation)
o LP optimal value ≥ ILP optimal value (for maximization) ➢ 𝑥∗ = LP optimal solution
➢ Round 𝑥∗ to 𝑥ො such that 𝑐𝑇𝑥ො ≥ 𝑐𝑇𝑥∗ ≥ ILP optimal value 𝜌𝜌
➢ Gives 𝜌-approximation
o Info: Best 𝜌 you can hope to get via this approach for a particular LP-ILP combination is called the integrality gap
373F20 - Nisarg Shah 50
Local Search Paradigm
373F20 - Nisarg Shah 51
Local Search
• Heuristic paradigm
➢ Sometimes it might provably return an optimal solution ➢ But even if not, it might give a good approximation
• Template
➢ ➢ ➢
Start with some initial feasible solution 𝑆
While there is a “better” solution 𝑆′ in the local neighborhood of 𝑆
Switch to 𝑆’
• Need to define:
➢ Which initial feasible solution should we start from?
➢ What is “better”?
➢ What is “local neighborhood”?
373F20 - Nisarg Shah 52
Local Search
• For some problems, local search provably returns an optimal solution
• Example: network flow
➢ Initial solution: zero flow
➢ Local neighborhood: all flows that can be obtained by augmenting the current flow along a path in the residual graph
➢ Better: Higher flow value
• Example: LP via simplex
➢ Initial solution: a vertex of the polytope
➢ Local neighborhood: neighboring vertices ➢ Better: better objective value
373F20 - Nisarg Shah 53
Local Search
• But sometimes it doesn’t return an optimal solution, and “gets stuck” in a local maxima
373F20 - Nisarg Shah 54
Local Search
• In that case, we want to bound the worst-case ratio between the global optimum and the worst local optimum (the worst solution that local search might return)
Worst ratio
373F20 - Nisarg Shah 55
Max-Cut
373F20 - Nisarg Shah 56
Max-Cut
• Problem
➢ Input: An undirected graph 𝐺 = (𝑉, 𝐸)
➢ Output: A partition (𝐴, 𝐵) of 𝑉 that maximizes the number of edges going across the cut, i.e., maximizes |𝐸′| where 𝐸′ = { 𝑢, 𝑣 ∈
𝐸 | 𝑢 ∈ 𝐴, 𝑣 ∈ 𝐵}
➢ This is also known to be an NP-hard problem
➢ What is a natural local search algorithm for this problem?
o Given a current partition, what small change can you do to improve the objective value?
373F20 - Nisarg Shah 57
Max-Cut
• Local Search
➢ Initialize (𝐴, 𝐵) arbitrarily.
➢ While there is a vertex 𝑢 such that moving 𝑢 to the other side improves the objective value:
o Move 𝑢 to the other side.
• When does moving 𝑢, say from 𝐴 to 𝐵, improve the objective value?
➢ When 𝑢 has more incident edges going within the cut than across the cut, i.e., when 𝑢, 𝑣 ∈ 𝐸 𝑣 ∈ 𝐴 > 𝑢, 𝑣 ∈ 𝐸 𝑣 ∈ 𝐵
373F20 – Nisarg Shah 58
Max-Cut
• Local Search
➢ Initialize (𝐴, 𝐵) arbitrarily.
➢ While there is a vertex 𝑢 such that moving 𝑢 to the other side improves the objective value:
o Move 𝑢 to the other side.
• Why does the algorithm stop?
➢ Every iteration increases the number of edges across the cut by at least 1, so the algorithm must stop in at most |𝐸| iterations
373F20 – Nisarg Shah 59
Max-Cut
• Local Search
➢ Initialize (𝐴, 𝐵) arbitrarily.
➢ While there is a vertex 𝑢 such that moving 𝑢 to the other side improves the objective value:
o Move 𝑢 to the other side.
• Approximation ratio?
➢ At the end, every vertex has at least as many edges going across the
cut as within the cut
➢ Hence, at least half of all edges must be going across the cut
o Exercise: Prove this formally by writing equations.
373F20 – Nisarg Shah 60
Weighted Max-Cut
• Variant
➢ Now we’re given integral edge weights 𝑤: 𝐸 → N
➢ The goal is to maximize the total weight of edges going across the cut
• Algorithm
➢ The same algorithm works…
➢ But we move 𝑢 to the other side if the total weight of its incident edges going within the cut is greater than the total weight of its incident edges going across the cut
373F20 – Nisarg Shah 61
Weighted Max-Cut
• Number of iterations?
➢ Unweighted case: #edges going across the cut must increase by at
least 1, so it takes at most |𝐸| iterations
➢ Weighted case: total weight of edges going across the cut must
increase by at least 1, but this could take up to σ 𝑤
iterations,
which can be exponential in the input length
o There are examples where the local search actually takes
exponentially many steps
o Fun exercise: Design an example where the number of iterations is exponential in the input length.
𝑒∈𝐸 𝑒
373F20 – Nisarg Shah 62
Weighted Max-Cut
• Number of iterations?
➢ But we can find a 2 + 𝜖 approximation in time polynomial in the
input length and 1 𝜖
➢ The idea is to only move vertices when it “sufficiently improves” the objective value
373F20 – Nisarg Shah 63
Weighted Max-Cut
• Better approximations?
➢ Theorem [Goemans-Williamson 1995]:
There exists a polynomial time algorithm for max-cut with approximation ratio 2 ⋅ min 𝜃 ≈ 0.878
o Uses “semidefinite programming” and “randomized rounding”
o Note: The literature from here on uses approximation ratios ≤ 1,
so we will follow that convention in the remaining slides.
➢ Assuming the unique games conjecture, this approximation ratio is tight
𝜋 0≤𝜃≤𝜋 1−cos 𝜃
373F20 – Nisarg Shah 64
Exact Max-𝑘-SAT
373F20 – Nisarg Shah 65
Exact Max-𝑘-SAT
• Problem
➢ Input: An exact 𝑘-SAT formula 𝜑 = 𝐶 ∧ 𝐶 ∧ ⋯ ∧ 𝐶 ,
12𝑚
where each clause 𝐶 has exactly 𝑘 literals, and a weight 𝑤 ≥ 0 of
𝑖𝑖
➢ Output: A truth assignment 𝜏 maximizing the total weight of clauses
each clause 𝐶 𝑖
satisfied under 𝜏
➢ Let us denote by 𝑊(𝜏) the total weight of clauses satisfied under 𝜏 ➢ What is a good definition of “local neighborhood”?
373F20 – Nisarg Shah 66
Exact Max-𝑘-SAT
• Local neighborhood:
➢ 𝑁 (𝜏) = set of all truth assignments 𝜏′ which differ from 𝜏 in the
𝑑
values of at most 𝑑 variables
23 • Theorem: The local search with 𝑑 = 1 gives a Τ
approximation to Exact Max-2-SAT.
373F20 – Nisarg Shah 67
Exact Max-𝑘-SAT
• Theorem: The local search with 𝑑 = 1 gives a Τ
approximation to Exact Max-2-SAT.
• Proof:
➢ Let 𝜏 be a local optimum
o 𝑆0 = set of clauses not satisfied under 𝜏
o 𝑆 = set of clauses from which exactly one literal is true under 𝜏
1
o 𝑆2 = set of clauses from which both literals are true under 𝜏
o 𝑊 𝑆 , 𝑊 𝑆 , 𝑊 𝑆 be the corresponding total weights 012
2
• Equivalently,𝑊𝑆 ≤ Τ ⋅ 𝑊𝑆 +𝑊𝑆 +𝑊𝑆 013012
23
oGoal:𝑊𝑆 +𝑊𝑆 ≥Τ⋅𝑊𝑆 +𝑊𝑆 +𝑊𝑆 123012
373F20 – Nisarg Shah 68
Exact Max-𝑘-SAT
• Theorem: The local search with 𝑑 = 1 gives a Τ
approximation to Exact Max-2-SAT.
• Proof:
➢ We say that clause 𝐶 “involves” variable 𝑗 if it contains 𝑥 or 𝑥ഥ
➢ 𝐴 = set of clauses in 𝑆 involving variable 𝑗 𝑗0
o Let 𝑊 𝐴 be the total weight of such clauses 𝑗
➢ 𝐵 = set of clauses in 𝑆 involving variable 𝑗 such that it is the literal 𝑗1
of variable 𝑗 that is true under 𝜏
o Let 𝑊 𝐵 be the total weight of such clauses 𝑗
23
𝑗𝑗
373F20 – Nisarg Shah 69
Exact Max-𝑘-SAT
• Theorem: The local search with 𝑑 = 1 gives a Τ
approximation to Exact Max-2-SAT.
• Proof:
➢2𝑊𝑆 =σ𝑊𝐴
o Every clause in 𝑆0 is counted twice on the RHS ➢𝑊𝑆 =σ𝑊𝐵
23
0𝑗𝑗
1𝑗𝑗
o Every clause in 𝑆 is only counted once on the RHS for the variable 1
whose literal was true under 𝜏 ➢Foreach𝑗:𝑊 𝐴 ≤𝑊 𝐵
𝑗𝑗
o From local optimality of 𝜏, since otherwise flipping the truth value of variable 𝑗 would have increased the total weight
373F20 – Nisarg Shah 70
Exact Max-𝑘-SAT
• Theorem: The local search with 𝑑 = 1 gives a Τ
23
o Summing the third equation on the last slide over all 𝑗, and then
approximation to Exact Max-2-SAT.
• Proof:
➢2𝑊𝑆 ≤𝑊𝑆
01
using the first two equations on the last slide ➢ Hence:
o3𝑊𝑆 ≤𝑊𝑆 +𝑊𝑆 ≤𝑊𝑆 +𝑊𝑆 +𝑊𝑆 001012
o Precisely the condition we wanted to prove… o QED!
373F20 – Nisarg Shah 71
Exact Max-𝑘-SAT
• Higher 𝑑?
➢ Searches over a larger neighborhood
➢ May get a better approximation ratio, but increases the running time as we now need to check if any neighbor in a large neighborhood provides a better objective
➢ The bound is still 2/3 for 𝑑 = 𝑜(𝑛)
➢ For 𝑑 = Ω 𝑛 , the neighborhood size is exponential
➢ But the approximation ratio is…
oAtmost4/5with𝑑< Τ 2
𝑛
o 1 (i.e. optimal solution is always reached) with 𝑑 = Τ 2
𝑛
373F20 - Nisarg Shah 72
Exact Max-𝑘-SAT
• Better approximation ratio?
➢ We can learn something from our proof
➢ Note that we did not use anything about 𝑊 𝑆2 , and simply added it at the end
➢Ifwecouldalsoguaranteethat𝑊 𝑆0 ≤𝑊 𝑆2 ...
o Then we would get 4 𝑊 𝑆 ≤ 𝑊 𝑆 + 𝑊 𝑆 + 𝑊 𝑆 , which
3
➢ Result (without proof):
o This can be done by including just one more assignment in the
neighborhood: 𝑁 𝜏 = 𝑁 𝜏 ∪ 𝜏𝑐 , where 𝜏𝑐 = complement of 𝜏 1
would give a Τ approximation 4
0012
373F20 - Nisarg Shah 73
Exact Max-𝑘-SAT
• What if we do not want to modify the neighborhood?
➢ A slightly different tweak also works
➢ We want to weigh clauses in 𝑊(𝑆2) more because when we get a clause through 𝑆2, we get more robustness (it can withstand changes in single variables)
• Modified local search:
➢ Start at arbitrary 𝜏
➢ While there is an assignment in 𝑁 𝜏
1.5𝑊𝑆 +2𝑊(𝑆) 12
o Switch to that assignment
that improves the potential
1
373F20 - Nisarg Shah 74
Exact Max-𝑘-SAT
• Modified local search:
➢ Start at arbitrary 𝜏
➢ While there is an assignment in 𝑁 𝜏
1.5𝑊𝑆 +2𝑊(𝑆) 12
o Switch to that assignment • Note:
that improves the potential
1
➢ This is the first time that we’re using a definition of “better” in local search paradigm that does not quite align with the ultimate objective we want to maximize
➢ This is called “non-oblivious local search”
373F20 - Nisarg Shah 75
Exact Max-𝑘-SAT
• Modified local search:
➢ Start at arbitrary 𝜏
➢ While there is an assignment in 𝑁 𝜏
1.5𝑊𝑆 +2𝑊(𝑆) 12
o Switch to that assignment • Result (without proof):
that improves the potential
1
3
➢ Modified local search gives Τ -approximation to Exact Max-2-SAT 4
373F20 - Nisarg Shah 76
Exact Max-𝑘-SAT
• More generally:
➢ The same technique works for higher values of 𝑘
➢ Gives 2𝑘−1 approximation for Exact Max-𝑘-SAT 2𝑘
o In the next lecture, we will achieve the same approximation ratio much more easily through a different technique
78
• Note: This ratio is Τ for Exact Max-3-SAT
7
➢ Theorem [Håstad]: Achieving Τ + 𝜖 approximation where 𝜖 > 0 is
NP-hard.
o Uses PCP (probabilistically checkable proofs) technique
8
373F20 – Nisarg Shah 77