Minimum weight submodular cover
This week we study the minimum weight submodular cover prob- lem, a generalizations of the minimum weight set cover problem.
12.1 Minimum set cover
The input of the minimum weight set cover problem is a collection of subsets S = {S1,…,Sm} of some ground set U and a weight function w : S → R+. The goal is to pick a minimum weight collection of subsets C ⊆ S whose union equals U:
The minimum set cover problem
is closely related to the maximum coverage problem. In the former we want to cover the whole ground set with a minimum number of subsets, while in the latter we have a strict budget for how many subsets we can use and we aim to maximize the number of elements covered.
minimize w(C) such that
To get some intuition, we first consider the unweighted version where w(Si) = 1 for all subsets in S. Notice that the objective
in this case is to minimize the number of subsets used. Again we study a very simple greedy heuristic.
This algorithm is very similar to the greedy algorithm for maxi- mum coverage. Indeed, the only difference is the termination con- dition of the while loop. In fact, we can use some of the properties we derived last week. Let (U, S ) be an instance of the minimum set cover problem. Suppose the optimal solution uses opt sets. Let Xi be the set of elements covered by greedy-cardinality after i iterations. Then
© Copyright 2021 Julián Mestre. ThisworkislicensedunderaCreative
Commons Attribution-NonCommercial- ShareAlike 4.0 International License.
1: 2: 3: 4: 5: 6:
functiongreedy-cardinality(U,S) C←∅
while T∈C T < |U| do
let S ∈ S be a subset maximizing S \ T∈C T add S to C
|Xi| ≥ |U| ·
To justify this inequality, define an instance of the maximum coverage instance where we need to pick opt sets and the optimal
week 12 – minimum weight submodular cover
discrete optimization 2
solution covers the whole ground set. Then apply Exercise 1 from Week ?? to this auxiliary instance.
We claim that greedy-cardinality terminates after ⌈ln|U|⌉ opt iterations. Indeed, X⌈ln |U|⌉ opt must equal U since
X ≥ |U| · 1− 1−
1 ⌈ln|U|⌉opt opt
Hereweagainweusethefactthat the series 1 − n1 n is increasing and convergesto e1.
1 See Exercise 1 for a precise statement of the best known hardness result for set cover.
⌈ln |U|⌉ opt
1ln|U| >|U|· 1− e
1 =|U|· 1−|U|
Therefore, greedy-cardinality is a ⌈ln |U|⌉-approximation algo- rithm for the set cover problem. Surprising, this is essentially the best possible approximation factor for general instances1. However, we can get better approximations for some instances.
12.2 Minimum weight set cover
If we want to have a good approximation for the weighted version of set cover, our algorithm must take the set weights into account when building the solution. A natural choice is to look at cost we pay per newly covered element.
Theorem 12.1. Algorithm greedy is an H∆-approximation for minimum weight set cover, where ∆ = maxS∈S |S|.
Here Hn denotes the nth Harmonic number2 H n = 1 + 12 + · · · + n1 ,
which grows logarithmically with n; more precisely, Hn = ln n+γ+o(1),
where γ ≈ 0.5773 is the Euler-Mascheroni constant constant3. The high level idea of the analysis will be to charge the cost
of the solution greedy builds to the elements of U in such a way that every set O in the optimal solution receives at most H∆w(O) charge.
Consider an iteration of greedy where S is added to C, then we split the cost of S among the newly covered elements as follows
2 Harmonic number, Wikipedia.
3 Euler-Mascheroni constant, Wikipedia.
1: 2: 3: 4: 5: 6:
functiongreedy(w,U,S) C←∅
while T∈C T < |U| do
let S ∈ S be a subset minimizing w(S)
add S to C return C
|S\T∈C T|
bill(j) = |S \ T ∈C T | , for each j ∈ S \
week 12 – minimum weight submodular cover discrete optimization
Adding up all the bills we get the weight of the greedy solution
w(greedy) =
Let O be an optimal solution and O = {o1,...,ol} be an arbitrary A1 set in it. Assume greedy covers the elements in O in the order
⟨o1, o2, . . . , ol⟩. Let Ai be the first set picked by greedy covering
element oi, and let Xi be the set of elements that where already
covered just before Ai was chosen. Because the algorithm selects sets greedily we have
w(Ai) ≤ w(O) ≤ w(O) = w(O) . |Ai \Xi| |O\Xi| |{oi,...,ol}| l−i+1
Notice that the leftmost term is the bill that oi receives, so
l bill(O) =
bill(oi) ≤
The approximation factor of greedy follows immediately
l−i+1 = Hl w(O). w(greedy) = bill(j)
≤ bill(j) O∈O j∈O
≤ H|O| w(O) O∈O
≤ H∆ w(O) 12.3 Minimum submodular cover
Given a monotone non-decreasing submodular subset function
f : 2U → RdefinedonthepowersetofagroundsetUanda weight function w : U → R+, we consider the problem of finding a maximizer C of f having minimum weight; that is,
minimize w(C) such that f(C) = f(U). (12.2)
We call this the minimum weight submodular cover problem. The greedy algorithm from the previous section can be adapted to this more general problem. Again, we pick items greedily so that we pay the least per unit of f-value increase.
We use the following shorthand notation ρj(S) = f(S + j) − f(S). It can be regarded as the benefit of adding j to S.
1: 2: 3: 4: 5: 6:
functiongreedy-submodular(w,U,f) C←∅
while f(C) < f(U) do
let j ∈ U be an element minimizing wj f(C+j)−f(C)
add j to C return C
week 12 – minimum weight submodular cover
discrete optimization 4
Theorem12.2. Algorithmgreedy-submodularisan(1+ln∆)- approximation for minimum weight submodular cover, where
We can equivalently defined ∆ as
maximize subject to
∀j ∈ U ∀S⊆U
∆ = max j∈U
min ρj (S))
max max S:ρj(S)>0
j∈U min S:ρj(S)>0
ρj (S) ρj(S)
Theorem 12.3. When f is integer-valued, Algorithm greedy-submodular
is an H∆-approximation for minimum weight submodular cover, where ∆ = max ρj(∅).
which obscures its value a bit but looks more symmetrical.
Consider the following integer program for our problem
minimize subject to
ρj(S)xj ≥ f(U)−f(S)
∀S ⊆ U ∀j∈U
To show that this a correct formulation for our problem we only need to show that for C ⊆ U and its characteristic vector χC it holds that f(C) = f(U) if and only if χC is a feasible solution of (IP).
Indeed, if χC is feasible, the constraint for S = C means
ρj(C) χj = 0 and therefore f(C) = f(U).
For other direction, if f(C) = f(U) then for any S ⊆ U we have C
f(U) − f(C) ≤
f(U) − f(S) = f(C) − f(S) ≤ ρj(S) = j∈/C\S
The dual of its linear relaxation is
(f(U) − f(S)) yS S⊆U
ρj(S)yS ≤ wj S⊆U:j∈/S
ρj(S)χj . j∈/S
Suppose the algorithm picks items C = {j1, j2, . . . , jT } in this
order. We define a sequence of sets S0 ⊆ S1 ⊆ ··· ⊆ ST as follows Si = {j1,…,ji},
and the benefit of element ji as
θi=wji =wji.
f(Si) − f(Si−1) ρji (Si−1) Finally, we define a dual solution
yS =θi+1−θi 0
if S = S0,
ifS=Si for0
ρj(S)yS ≤α·wj ∀j∈U. S⊆U:j∈/S
This will imply that C is an α-approximation, since αy is a feasible dual solution that can pay for a α1 fraction of the cost of C.
Forsomej ∈ U,letrbesuchthatρj(Sr) > 0butρj(Sr+1) = 0; notice that 0 ≤ r < T. Then the dual constraint for j is
ρj(S)yS = ρj(Si)ySi,
S⊆U:j∈/S i=0
= ρj(S0) θ1 +
θi (f(Si) − f(Si−1)), wji
You may want to take a minute to convince yourself that the second equality holds.
≤ wj · ρj(Si−1) − ρj(Si),
i=1 ρj (Si−1 )
where the last inequality follows from the way greedy-submodular
picks its elements, which gives us θi ≤ wj
ρj (Si−1 )
For x ∈ (0, ρj(∅)] we define the function
h(x) = so that
ρj(Si−1) r+1
by x1 and δ1: h(x)
ρj(Si) (θi+1 − θi), (ρj(Si−1) − ρj(Si)) θi,
Note that h(x) can be upperbounded
ρj (S2 )−ρj (S3 )
1 , where i is such that ρj(Si) < x ≤ ρj(Si−1),
ρj(Si−1) − ρj(Si)
ρj (Si−1 )
Notice that h(x) can be upperbounded by x1 and δ1 , where δ =
minS:ρj(S)>0 ρj(S). We can use this to bound the factor by which the constraint for j is violated
ρj(Si−1) − ρj(Si)
= 1+ln ρj(∅). δ
ρj(∅) i=1 ji−1 0
h(x)dx, ρj(∅) 1
≤δdx+ xdx,
week 12 – minimum weight submodular cover
discrete optimization 6
If f is integer value, we can get a a slightly better bound by not- ing that in this case h(x) ≤ 1 , in which case we get
ρj(Si−1) − ρj(Si)
Therefore, while y is not a feasible dual solution αy is, where
ρj (Si−1 )
α is the appropriate scaling constant depending on whether f is
fractional or integer-valued. It follows that (f(U) − f(S)) yS is S⊆U α
a lower bound on the cost of the optimal solution O. Putting these observations together, we get
w(greedy-submodular)=α·
12.4 Applications Minimum spanning tree
yS (f(U)−f(S))α ≤α·w(O)
Let G = (V,E) be a connected graph with edges weights w : E → R+. Let us denote with C(H) the collection of connected compo- nents of some graph H. For any subset of edges S ⊆ E we define
f(S) = (|A| − 1). A∈C(V ,S)
We claim that this function is submodular4 and monotone non- decreasing. Note that f(E) = n − 1, and any subset S ⊆ E such that f(S) = n − 1 spans the vertex set. This mean the minimum weight submodular cover problem that f captures is the minimum weight spanning tree problem. Furthermore, f({e}) − f(∅) = 1 for all edges e ∈ E, which gives us the following corollary.
Corollary 12.1. Algorithm greedy-submodular is a 1-approximation for the minimum weight spanning subgraph problem.
What does a 1-approximation mean? It means the algorithm is optimal! The corollary should not be surprising since greedy- submodular for this particular function f behaves exactly like Kruskal’s algorithm5.
Connected vertex cover
Let G = (V,E) be a connected graph with vertex weights w : V → R+. The minimum weight connected vertex cover problem is to find a minimum weight subset of vertices S such that S is a vertex cover6 and (S, E(S)) is connected.
For a subset of the vertices S ⊆ V let us define f(S) to be the number of edges covered by S minus the number of connected
4 Indeed, this nothing but the rank function of the graphical matroid defined by G. In the Exercises you will have to prove that the rank function defined by any matroid is submodular.
5 Kurskal’s algorithm, Wikipedia.
6 Recall that S is a vertex cover if for all (u,v)∈Eeitheru∈Sorv∈S. Thatis, we use vertices to cover edges.
week 12 – minimum weight submodular cover
discrete optimization 7
components of the graph induced by S; that is,
f(S) = |{(u,v) ∈ E : u ∈ S or v ∈ S}|−|C(S,E(S))|.
Now consider the benefit of adding a vertex u ∈/ S to our so- lution. Adding u will affect the number of edges covered and will change the structure of the connected components.
f(S+u)−f(S) = |N(u)\S|+
|{A ∈ C(S,E(S)) : A∩N(u) ̸= ∅}| − 1
First,noticethatforallS⊆V andu∈V\Swehave f(S+u)−f(S) ≥ 0.
Thus, f is monotone non-decreasing. Second,forallS⊆T andu∈V\T weclaimthat
f(T +u)−f(T) ≤ f(S+u)−f(S)
Indeed, the first term of (12.3) can only go up when we go from
T to S since N(u)\T ⊆ N(u)\S, and while the second term can go up, it must be accompanied by a matching decrease of the first term.
Corollary 12.2. Algorithm greedy-submodular is an H∆-approximation for minimum weight connected vertex cover, where ∆ = maxu∈V deg(u) − 1.
Landmark selection
Imagine a robot trying to navigate an undirected network G = (V,E). The robot can move from node to node in G. It does not know the name of the location it is currently located, but it can measure its current distance to some set of landmarks L ⊆ V. We would like the robot to be able to correctly identify its location only based on the vector of distances to the landmarks. Essentially, we want that for every two different vertices u, v ∈ V there is always a landmark that distinguishes them; that is, we want that
∃z ∈ L : d(z,u) ̸= d(z,v),
where d is the shortest (in terms of number of edges) path distance in G. The objective of the minimum landmark selection problem is find a minimum cardinality landmark set.
For any subset of vertices S ⊆ V let us define f(S) to be the number of pair of vertices that S distinguishes:
f(S)=|{(u,v)∈V×V :∃z∈L:d(z,u)̸=d(z,v)}|
It is not difficult to see that f is monotone non-decreasing and submodular7. Notice that f(u) ≤ n2, so the approximation factor of greedy-submodular is
Hn2 = lnn2 +γ+o(1) = 2lnn+γ+o(1).
7 In fact, this is nothing but the sub- modular function interpretation of a minimum set cover instance!
week 12 – minimum weight submodular cover
discrete optimization 8
One can do slightly better by using a different function. For a particular subset of landmarks S we construct the relation R ⊆ V×V
u R v ≡ ∀ z ∈ S : d(u, z) = d(v, z).
Let A1,A2,…,Ak be the equivalence classes of R. Then we let f be
It can be shown that f is submodular and monotone non-decreasing. Furthermore, f(∅) = − log2 n! and f(V) = 0 and ρj(S) ≥ 1 for all
S such that ρj(S) > 0. It follows that greedy-submodular has an approximation factor of
ln log2 n!+1 = lnn+lnlnn+Θ(1).
1. It is know that if there is a ρ-approximation for the minimum set cover where ρ = (1 − ε) ln |U| then P = NP. Prove that this imples that if there is a 1 − e1 + ε-approximation for maximum coverage then P = NP.
2. Consider the following linear relaxation for the minimum weight set cover problem
Its dual is
minimize subjectto
maximize subjectto
xS ≥1 ∀i∈U S∈S :i∈S
xS ≥0 ∀S∈S
yi ≤wS ∀S∈S
yi ≥0 ∀i∈S
f(S) = − log2
|Ai|! (12.4)
Argue that the dual solution yi = bill(i) has enough value to pay for the solution constructed by greedy but violates the dual constraints by an H∆ factor.
3. Let G = (V,E) be a connected undirected graph with vertex weights w : V → R+. The minimum weight connected dominated set problem is to find a minimum weight subset of vertices S such that S is a dominating set8 and (S, E(S)) is connected.
It could be tempting to try to fit this problem into the submodu- lar cover framework by defining
f(S) = |{u ∈ V : u ∈ S or N(u)∩S ̸= ∅}|−|C(S,E(S))|.
8 Recall that S is a dominating set if for all u ∈ V \ S we have N(u) ∩ S ̸= ∅.
week 12 – minimum weight submodular cover
discrete optimization 9
Prove that f is not submodular.
4. The partial set cover problem is similar to regular set cover ex- cept that we do not want to cover all the ground set, but just p fraction of U for some input parameter p ∈ (0, 1).
Show how to model this problem with the submodular cover framework. What is the greedy criterion in the “language” of the partial cover problem?
5. The set multi-cover problem is similar to regular set cover except that each element i in the ground set has to be covered at least ki times specified by the input.
Show how to model this problem with the sumbmodular cover framework. What is the greedy criterion in the “language” of the set multi-cover problem?
* 6. Prove that the set function defined by (12.4) is submodular and monotone non-decreasing.
7. Prove that for the set function f defined by (12.4) it holds that f(∅) = −log2n!,f(V) = 0andρj(S) ≥ 1forallSsuchthat ρj(S) > 0.
8. Prove that the rank function of a matroid is submodular.