Approximation Algorithms
2021-03-29 CSC373 Winter 2021 – Sam Toueg 1
Min Vertex Cover and
Max Matching
2021-03-29 CSC373 Winter 2021 – Sam Toueg 2
Vertex Cover
• 𝐺 = (𝑉, 𝐸): undirected graph
• vertex cover (VC): a subset 𝑉′ of the nodes of 𝐺 that “touches’’ every edge of 𝐺, i.e., every edge has at least one endpoint in 𝑉′
• minimum vertex cover: a VC with minimum size
2021-03-29 CSC373 Winter 2021 – Sam Toueg 3
Matching
𝐺 = (𝑉, 𝐸): undirected graph
• Amatching𝑀in𝐺isasubsetofedgesof𝐺suchthat
no two edges are incident on (“share’’) the same node • Maximum matching: a matching of maximum size
2021-03-29 CSC373 Winter 2021 – Sam Toueg 4
Vertex Cover versus Matching
In the lecture “Bipartite Matching” (Network Flow Applications) we proved the following:
Claim:Foranymatching𝑀in𝐺,andanyVC𝑆of𝐺, 𝑀 ≤ 𝑆
Proof: Follows from:
• Every edge in 𝑀 must be covered by at least one node in 𝑆
• No node in 𝑆 can cover more than one edge of 𝑀
If a node of 𝑆 covers two edges of 𝑀 …
Then 𝑀 is not a matching!
2021-03-29 CSC373 Winter 2021 – Sam Toueg 5
Min Vertex Cover and Max Matching
• Problem:
ØInput: Undirected graph 𝐺 = (𝑉, 𝐸) ØOutput: A minimum vertex cover 𝑆 of 𝐺
• We already proved that this problem is NP-Complete
• But is there a good approximation algorithm?
• Try the greedy approach
• But how exactly?
2021-03-29 CSC373CSWC3in7t3erW2i0n2te1r-2S0a2m0 Toueg 22
Min Vertex Cover and Max Matching • Greedy “edge-selection’’ algorithm for VC
Incrementally build a vertex cover 𝑆 as follows:
ØStart with 𝑆 = ∅
Ø While there exists an edge (𝑢, 𝑣) that is not yet “covered’’ by the nodes already in 𝑆, add both 𝑢 and 𝑣 to 𝑆
• But:
Ø Why are we “selecting’’ edges rather than vertices?
Ø Why are we adding both endpoints? Ø We’ll see…
2021-03-29 CSC373 Winter 2021 – Sam Toueg 23
Min Vertex Cover and Max Matchingd Max Matc
Greedy-Vertex-Cover𝐺 𝑆←∅; 𝑀←∅
𝐸# ← 𝐸
While (𝐸# ≠ ∅)
let (𝑢, 𝑣) be any edge in 𝐸#
𝑆 ← 𝑆 ∪ 𝑢 ∪ {𝑣}
𝑀←𝑀 ∪{(𝑢,𝑣)}
delete from 𝐸# every edge incident to 𝑢 or 𝑣
Return 𝑆
2021-03-29 CSC373 Winter 2021 – Sam Toueg 25
forundirectedgraph𝐺= 𝑉,𝐸 Edges that are not yet covered
byanynodein𝑆
vertex cover nodes that we added so far
We also build a matching 𝑀! Why??
Min Vertex Cover and Max Matching
Greedy-Vertex-Cover 𝑮 𝑆 ← ∅; 𝑀 ← ∅
𝐸! ←𝐸 !
While(𝐸 ≠∅) !
let (𝑢, 𝑣) be any edge in 𝐸
𝑆 ← 𝑆 ∪ 𝑢 ∪ {𝑣}
𝑀←𝑀 ∪{(𝑢,𝑣)}
delete from 𝐸! every edge incident to 𝑢 or 𝑣
• At the end of this algorithm: Ø 𝑆 is indeed a set cover of 𝐺 Ø𝑀isamatchingof𝐺 Ø|𝑆|=2⋅ 𝑀
Return 𝑆 Claim1(alreadyproved):∀matching𝑀of𝐺and∀vertexcover𝑆of𝐺:|𝑀|≤ 𝑆
Theorem:
This is a 2-approximation algorithm for the minimum vertex cover problem. Proof:
Let 𝑆 = vertex cover returned by this algorithm Let 𝑀 = matching returned by this algorithm Bythealgorithm: 𝑆 =2⋅|𝑀|
Let 𝑆∗ = minimum vertex cover
ByClaim1:|𝑀|≤ 𝑆∗
So: 𝑆 ≤ 2 ⋅ |𝑆∗| Q.E.D. 2021-03-29
CSC373 Winter 2021 – Sam Toueg 26
Min Vertex Cover
• Theorem [Dinur-Safra 2004]:
Ø Unless P = NP, there is no polynomial-time 𝜌-approximation
algorithm for vertex cover for any 𝜌 < 1.3606.
2021-03-29 CSC373 Winter 2021 - Sam Toueg 29
Weighted Vertex Cover
2021-03-29 CSC373 Winter 2020 31
Weighted Vertex Cover
• Problem
Ø Input: Undirected graph 𝐺 = (𝑉, 𝐸), weights 𝑤 ∶ 𝑉 → 𝑅,- Ø Output: Vertex cover 𝑆 of minimum total weight
• This is a generalization of the unweighted vertex cover problem, which is already NP-Complete!
• The previous greedy algorithm doesn’t work Ø Gives arbitrarily bad approximation
Ø Need another strategy...
2021-03-29 CSC373 Winter 2021 - Sam Toueg 32
ILP Formulation ØForeachvertex𝑣,createabinaryvariable𝑥.∈ 0,1
indicating whether vertex 𝑣 is chosen in the vertex cover
Ø Then, computing the min weight vertex cover is equivalent to
solving the following Integer Linear Program (ILP) min Σ. 𝑤. ⋅ 𝑥.
subject to:
subject to:
𝑥 +𝑥 ≥1, 𝑥/+𝑥.≥1,
∀𝑢,𝑣 ∈𝐸
/.
∀𝑢,𝑣 ∈𝐸
𝑥 ∈ 0,1, 𝑥.∈ 0,1,
∀𝑣∈𝑉
.
∀𝑣∈𝑉
Ø But ILP is NP-Complete...
2021-03-29 CSC373 Winter 2021 - Sam Toueg 34
LP Relaxation
• What if, instead of the original ILP, we solve this LP?
ILP with binary variables
LP with real variables
minΣ. 𝑤. ⋅𝑥. subject to
𝑥/+𝑥.≥1, 𝑥. ∈ 0,1 ,
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
minΣ. 𝑤. ⋅𝑥. subject to
𝑥/+𝑥.≥1, 𝑥. ≥ 0,
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
2021-03-29
CSC373 Winter 2021 - Sam Toueg
35
LP Relaxation
• What if, instead of the original ILP, we solve this LP?
ILP with binary variables
LP with real variables
minΣ. 𝑤. ⋅𝑥. subject to
𝑥/+𝑥.≥1, 𝑥. ∈ 0,1 ,
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
minΣ. 𝑤. ⋅𝑥. subject to
𝑥/+𝑥.≥1, 𝑥. ≥ 0,
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
2021-03-29
CSC373 Winter 2021 - Sam Toueg
36
Rounding LP Solution
• What if, instead of the original ILP, we solve this LP?
Ø LP minimizes same objective over a larger feasible space
Ø So: optimal LP objective value ≤ optimal ILP objective value
Ø But optimal LP solution 𝑥∗ is not a binary vector!
Ø Can we round 𝑥∗ to some binary vector 𝑥R that is a solution to the ILP without increasing the objective value too much?
ILP with binary variables
LP with real variables
minΣ. 𝑤. ⋅𝑥.
subject to
𝑥/+𝑥.≥1,
𝑥. ∈ 0,1 ,
2021-03-29
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
minΣ. 𝑤. ⋅𝑥. subject to 𝑥/+𝑥.≥1, 𝑥. ≥ 0,
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
38
CSC373 Winter 2021 - Sam Toueg
Rounding LP Solution
• Consider the optimal solution 𝑥∗ of LP (𝑥∗: vector of reals) Ø Round 𝑥∗ into binary vector 𝑥R as follows:
Øforeach𝑣∈𝑉,𝑥R =S0, 𝑥.∗<0.5 . 1,𝑥.∗≥0.5
Ø Claim 1: 𝑥R is a feasible solution of ILP (i.e. a vertex cover) oForeveryedge 𝑢,𝑣 ∈𝐸,𝑥!∗ +𝑥#∗ ≥1(because𝑥∗ isasolutionofLP) oSoatleastoneof 𝑥!∗,𝑥#∗ isatleast0.5
oSoatleastoneof 𝑥3!,𝑥3# is1,andthus𝑥3! +𝑥3# ≥1
ILP with binary variables
LP with real variables
minΣ. 𝑤. ⋅𝑥.
subject to
𝑥/+𝑥.≥1,
𝑥. ∈ 0,1 ,
2021-03-29
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
minΣ. 𝑤. ⋅𝑥. subject to 𝑥/+𝑥.≥1, 𝑥. ≥ 0,
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
39
CSC373 Winter 2021 - Sam Toueg
Rounding LP Solution
• Consider the optimal solution 𝑥∗ of LP (𝑥∗: vector of reals) Ø Round 𝑥∗ into binary vector 𝑥R as follows:
Øforeach𝑣∈𝑉,𝑥R =S0, 𝑥.∗<0.5 . 1,𝑥.∗≥0.5
Ø Claim 1: 𝑥R is a feasible solution of ILP (i.e. a vertex cover)
ILP with binary variables
LP with real variables
minΣ. 𝑤. ⋅𝑥.
subject to
𝑥/+𝑥.≥1,
𝑥. ∈ 0,1 ,
2021-03-29
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
minΣ. 𝑤. ⋅𝑥. subject to 𝑥/+𝑥.≥1, 𝑥. ≥ 0,
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
40
CSC373 Winter 2021 - Sam Toueg
Rounding LP Solution
• Consider the optimal solution 𝑥∗ of LP (𝑥∗: vector of reals) Ø Round 𝑥∗ into binary vector 𝑥R as follows:
Øforeach𝑣∈𝑉,𝑥R =S0, 𝑥.∗<0.5 . 1,𝑥.∗≥0.5
Ø C l a i m 2 : ∑ . 𝑤 . ⋅ 𝑥R . ≤ ≤ 2 2 ∗ ∗ ∑ . 𝑤 . ⋅ 𝑥 .∗
o weight only increases when some 𝑥#∗ ∈ [0.5,1] is shifted up to 𝑥3# = 1 o at most doubling the variable, so at most doubling the weight ∎
ILP with binary variables
LP with real variables
minΣ. 𝑤. ⋅𝑥.
subject to
𝑥/+𝑥.≥1,
𝑥. ∈ 0,1 ,
2021-03-29
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
minΣ. 𝑤. ⋅𝑥. subject to 𝑥/+𝑥.≥1, 𝑥. ≥ 0,
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
42
CSC373 Winter 2021 - Sam Toueg
Rounding LP Solution
• Consider the optimal solution 𝑥∗ of LP (𝑥∗: vector of reals) Ø Round 𝑥∗ into binary vector 𝑥R as follows:
Øforeach𝑣∈𝑉,𝑥R =S0, 𝑥.∗<0.5 . 1,𝑥.∗≥0.5
Ø C l a i m 2 : ∑ . 𝑤 . ⋅ 𝑥R . ≤ 2 ∗ ∑ . 𝑤 . ⋅ 𝑥 .∗ = 2 ∗ ( L P o p t i m a l v a l u e ) o weight only increases when some 𝑥#∗ ∈ [0.5,1] is shifted up to 𝑥3# = 1 o at most doubling the variable, so at most doubling the weight ∎
ILP with binary variables
LP with real variables
minΣ. 𝑤. ⋅𝑥.
subject to
𝑥/+𝑥.≥1,
𝑥. ∈ 0,1 ,
2021-03-29
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
minΣ. 𝑤. ⋅𝑥. subject to 𝑥/+𝑥.≥1, 𝑥. ≥ 0,
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
43
CSC373 Winter 2021 - Sam Toueg
Rounding LP Solution
• Consider the optimal solution 𝑥∗ of LP (𝑥∗: vector of reals) Ø Round 𝑥∗ into binary vector 𝑥R as follows:
Øforeach𝑣∈𝑉,𝑥R =S0, 𝑥.∗<0.5 . 1,𝑥.∗≥0.5
Ø C l a i m 2 : ∑ . 𝑤 . ⋅ 𝑥R . ≤ 2 ∗ ∑ . 𝑤 . ⋅ 𝑥 .∗ = 2 ∗ ( L P o p t i m a l v a l u e ) o weight only increases when some 𝑥#∗ ∈ [0.5,1] is shifted up to 𝑥3# = 1 o at most doubling the variable, so at most doubling the weight ∎
ILP with binary variables
LP with real variables
minΣ. 𝑤. ⋅𝑥.
subject to
𝑥/+𝑥.≥1,
𝑥. ∈ 0,1 ,
2021-03-29
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
minΣ. 𝑤. ⋅𝑥. subject to 𝑥/+𝑥.≥1, 𝑥. ≥ 0,
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
44
CSC373 Winter 2021 - Sam Toueg
Rounding LP Solution
• Consider the optimal solution 𝑥∗ of LP (𝑥∗: vector of reals) Ø Round 𝑥∗ into binary vector 𝑥R as follows:
Øforeach𝑣∈𝑉,𝑥R =S0, 𝑥.∗<0.5 . 1,𝑥.∗≥0.5
Ø C l a i m 2 : ∑ . 𝑤 . ⋅ 𝑥R . ≤ 2 ∗ ∑ . 𝑤 . ⋅ 𝑥 .∗ = 2 ∗ ( L P o p t i m a l v a l u e )
By Claims 1 and 2: (1) 𝑥R is a vertex cover and (2) its weight is at most 2 ∗ LP optimal value ≤ 2 ∗ ILP optimal value
⟹ weight of vertex cover 𝑥R ≤ 2 ∗ min weight vertex cover
ILP with binary variables
LP with real variables
minΣ. 𝑤. ⋅𝑥.
subject to
𝑥/+𝑥.≥1,
𝑥. ∈ 0,1 ,
2021-03-29
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
minΣ. 𝑤. ⋅𝑥. subject to 𝑥/+𝑥.≥1, 𝑥. ≥ 0,
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
45
CSC373 Winter 2021 - Sam Toueg
Rounding LP Solution
• Consider the optimal solution 𝑥∗ of LP (𝑥∗: vector of reals) Ø Round 𝑥∗ into binary vector 𝑥R as follows:
Øforeach𝑣∈𝑉,𝑥R =S0, 𝑥.∗<0.5 . 1,𝑥.∗≥0.5
• This gives a 2-approximation algorithm for the weighted vertex cover problem!
LP with real variables
Ø
ILP with binary variables
minΣ. 𝑤. ⋅𝑥.
subject to
𝑥/+𝑥.≥1,
𝑥. ∈ 0,1 ,
2021-03-29
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
minΣ. 𝑤. ⋅𝑥. subject to 𝑥/+𝑥.≥1, 𝑥. ≥ 0,
∀𝑢,𝑣 ∈𝐸 ∀𝑣 ∈ 𝑉
46
CSC373 Winter 2021 - Sam Toueg
General LP Relaxation Strategy
• If your NP-complete problem amounts to solving an ILP
Ø Max 𝑐$𝑥 subject to 𝐴𝑥 ≤ 𝑏, 𝑥 ∈ N (𝑥 is integer, need not be binary)
• Instead, solve the corresponding LP:
Ø Max 𝑐$𝑥 subject to 𝐴𝑥 ≤ 𝑏, 𝑥 ∈ R%& (LP relaxation)
o Note: LP optimal value ≥ ILP optimal value
Ø Let 𝑥∗ be the LP optimal solution i. e., 𝑐$𝑥∗ is the LP optimal value
Ø Round 𝑥∗ to an integer solution 𝑥3 such that:
o 𝑥" is still a feasible solution, i.e., 𝐴𝑥" ≤ 𝑏 #!$∗ LP optimal value
o For some approximation factor 𝜌 : 𝑐"𝑥" ≥ % = 𝜌 ≥
• This gives a 𝜌-approximation: 𝑐1𝑥R ≥ 234 56789:; <:;=> ?
ILP optimal value 𝜌
𝑥 is now allowed to be a non-negative real
𝑥A decreases LP optimal value by a factor of at most 𝜌
2021-03-29 CSC373 Winter 2021 – Sam Toueg
51