arXiv:1701.05339v2 [] 1 Feb 2017

Randomized Bicriteria Approximation Algorithm for
Minimum Submodular Cost Partial Multi-Cover
Problem
Yishuo Shi1, Zhao Zhang2∗, Ding-Zhu Du3
1

College of Mathematics and System Sciences, Xinjiang University
Urumqi, Xinjiang, 830046, China.

2

College of Mathematics Physics and Information Engineering, Zhejiang Normal University
Jinhua, Zhejiang, 321004, China.
Department of Computer Science, University of Texas at Dallas
Richardson, Texas, 75080, USA.

Abstract
This paper studies randomized approximation algorithm for a variant of the
set cover problem called minimum submodular cost partial multi-cover (SCPMC).
In a partial set cover problem, the goal is to find a minimum cost sub-collection
of sets covering at least a required fraction of elements. In a multi-cover problem,
each element e has a covering requirement re , and the goal is to find a minimum
cost sub-collection of sets S ′ which fully covers all elements, where an element
e is fully covered by S ′ if e belongs to at least re sets of S ′ . In a minimum
submodular cost set cover problem (SCSC), the cost function on sub-collection of
sets is submodular and the goal is to find a set cover with the minimum cost.
The SCPMC problem studied in this paper is a combination of the above three
problems, in which the cost function on sub-collection of sets is submodular and
the goal is to find a minimum cost sub-collection of sets which fully covers at
least q-percentage of all elements. Previous work shows that such a combination
enormously increases the difficulty of studies, even when the cost function is
linear.
In this paper, assuming that the maximum covering requirement rmax =
maxe re is a constant and the cost function is nonnegative, monotone nondecreasing, and submodular, we give the first randomized bicriteria algorithm for
SCPMC the output of which fully covers at least (q−ε)-percentage of all elements
and the performance ratio is O(b/ε) with a high probability, where b = maxe rfe
and f is the maximum number of sets containing a common element. The algorithm is based on a novel non-linear program. Furthermore, in the case when the
∗

Corresponding Author: Zhao Zhang, hxhzz@sina.com.

1

covering requirement r ≡ 1, a bicriteria O(f /ε)-approximation can be achieved
even when monotonicity requirement is dropped off from the cost function.
Keywords: partial cover, multi-cover, submodular cover, Lovász extension,
randomized algorithm, approximation algorithm, bicriteria.

1

Introduction

Set Cover is one of the most important combinatorial optimization problems in
both the theoretical field and the application field, the goal of which is to find a subcollection of sets with the minimum cost to cover all elements. There are a lot of
variants of the set cover problem. The minimum partial set cover problem (PSC) is to
find a minimum cost sub-collection of sets to cover at least q-percentage of all elements.
One motivation of PSC comes from the phenomenon that in a real world, “satisfying
all requirements” will be too costly or even impossible, because of resource limitation
or political policy. Another variant is the minimum multi-cover problem (MC), which
comes from the requirement of fault tolerance in practice. In MC, each element e has
a covering requirement re , and the goal is to find a minimum cost sub-collection S ′ to
fully cover all elements, where element e is fully covered by S ′ if e belongs to at least re
sets of S ′ . Another generalization of set cover is submodular cost set cover (SCSC), in
which the cost function on sub-collection of sets is submodular and the goal is to find
a set cover with the minimum cost. Submodular functions have a natural diminishing
returns property which finds wide applications in the real world, including economics,
game theory, machine learning and computer vision, etc.
In this paper, we consider a problem which is a combination of the above three
problems. In the minimum submodular cost partial multi-cover problem (SCPMC),
each element has a profit as well as a covering requirement, the goal is to find a
minimum submodular cost sub-collection of sets such that the profit of fully covered
elements is at least a fixed percentage of the total profit.

1.1

Related Work

For Set Cover, Hochbaum [9] gave an f –approximation algorithm based on LP
rounding where f is the maximum number of sets containing a common element. Khot
and Regev [13] showed that the set cover problem cannot be approximated within f −ε
for any constant ε > 0 assuming that unique games conjecture is true. Another classic
result on Set Cover is that greedy strategy yields a ln ∆-approximation [5, 11, 17],
where ∆ is the maximum cardinality of a set. Dinur and Steurer [4] showed that the
set cover problem cannot be approximated to (1 − o(1)) ln n unless P = NP , where n
is the size of ground set.
For MC, Dobson [6] gave an HK -approximation algorithm for the minimum multiset multi-cover
problem (MSMC), where K is the maximum size of a multi-set and
PK
HK = i=1 1/i is the harmonic number (recall that HK ≈ ln K). Rajagopalan and
2

Vazirani [18] gave a greedy algorithm achieving the same performance ratio, using
dual fitting analysis. For the minimum set k-cover problem in which the covering
requirement of every element is k, Berman et al. [2] gave a randomized algorithm
achieving expected performance ratio at most ln( ∆k ).
For PSC, Kearns [12] gave the first greedy algorithm achieving performance ratio
(2Hn +3). Refining the greedy algorithm, Slavik [21] improved the ratio to Hmin{⌈qn⌉,∆} ,
where q is the desired covering ratio. Using primal dual method, Gandhi et al. [8]
obtained an f -approximation. Bar-Yehuda [1] studied a generalized version of the
partial cover problem in which each element has a profit. Using local ratio method,
he also obtained an f -approximation. Proposing an Lagrangian relaxation framework,
Konemann et al. [14] gave a ( 43 + ε)H∆ -approximation for the generalized partial cover
problem.
From the above related work, it can be seen that both PSC and MC admit performance ratios which match those best ratios for the classic set cover problem. However,
combining partial cover with multi-cover seems to enormously increase the difficulty of
studies. Ran et al. [19] were the first to study approximation algorithm for the minimum partial multi-cover problem (PMC). Using greedy strategy and a delicate dual
fitting analysis, they gave a γH∆ -approximation algorithm, where γ = 1/(1 − (1 − q)η),
rmax
η = ∆ ccmax
, and cmax , cmin are the maximum and the minimum cost of set, rmax ,
min rmin
rmin are the maximum and the minimum covering requirement of element, respectively.
This ratio is meaningful only when the covering percentage q is very close to 1. In
[20], Ran et al. presented a simple greedy algorithm achieving performance ratio ∆.
Recall that in terms of ∆, greedy algorithm for Set Cover achieves performance ratio
ln ∆. So, ratio ∆ for PMC is exponentially larger than the one for Set Cover. In the
same paper, they also presented a local ratio algorithm which reveals an interesting
“shock wave” phenomenon: their performance ratio is f for both PSC (that is, when
rmax = rmin = 1 which is the partial single cover problem) and MC (that is, when
q = 1 which is the full multi-cover problem); however, when q is smaller than 1 by a
very small constant, the ratio jumps abruptly to O(n).
The submodular cost set cover problem was first proposed by Iwata and Nagano
[10]. They gave an f -approximation algorithm for nonnegative submodular functions.
In paper [15], Koufogiannakis and Young generalized set cover constraint to arbitrary
covering constraints and gave an f -approximation algorithm for monotone nondecreasing nonnegative submodular functions.
In this paper we combine submodular cost function with partial multi-cover constraint. As one can see from previous results on PMC, even when the cost function is
linear, the partial multi-cover problem is already very difficult.

1.2

Our Contribution

The major contribution of this paper is a randomized (ε, O( εb ))-approximation algorithm for SCPMC, that is, the algorithm produces a solution covering at least (q − ε)percentage of the total covering requirement, and achieves performance ratio O( εb )
3

with a high probability, where b = maxe
containing a common element.

f
re



, and f is the maximum number of sets

Before presenting this algorithm, we show that a natural integer program for
SCPMC does not work since its integrality gap is arbitrarily large. Hence, to obtain a good approximation, we propose a novel integer program. The relaxation of the
integer program uses Lovász extension [16]. Our algorithm consists of two stages of
rounding. The first stage is a deterministic rounding. The second stage is a random
rounding, the analysis of which is based on an equivalent expression of Lovász extension
[3] in view of expectation.
As far as we know, this is the first approximation algorithm for a partial version of
the submodular multi-cover problem. Furthermore, we show that for the special case
when the covering requirement r ≡ 1 (the special case is abbreviated as SCPSC), our
method can be adapted to yield an (ε, O(f /ε))-approximation with high probability,
even when monotonicity is dropped off from the requirement of the cost function.
This paper is organized as follows. In Section 2, we introduce formal definitions
of problems considered in this paper, as well as some technical results. The bicriteria
randomized algorithm for SCPMC is presented and analyzed in Section 3. In Section
4, we show how to adapt our algorithm to deal with SCPSC. The last section concludes
the paper and discusses some future work.

2

Preliminaries

Definition 2.1 (Submodular Cost Partial Multi-Cover (SCPMC)).
Suppose E is an
S
E
element set and S ⊆ 2 is a collection of subsets of E with S∈S S = E; each element
e ∈ E has a positive covering requirement re and a positive profit pe ; cost function
ρ0 : 2S 7→ R is defined on sub-collections of S, which is nonnegative, monotone nondecreasing, and submodular. Given a constant q ∈ (0, 1] called covering
ratio, the SCPMC
P
′
problem
is
to
find
a
minimum
cost
sub-collection
S
such
that
e∼S ′ p(e) ≥ qP , where
P
′
P = e∈E p(e) is the total profit, e ∼ S means that e is fully covered by S ′ , that is,
|{S ∈ S ′ : e ∈ S}| ≥ re . An instance of SCPMC is denoted as (E, S, r, p, q, ρ0 ).
In particular, when rmax = 1, we call the problem a submodular cost partial set
cover problem (SCPSC). When the cost function is linear, that
P is, every set S ∈ S has
a cost c(S) and the cost of a sub-collection S ′ is ρ0 (S ′ ) = S∈S ′ c(S), the problem is
exactly the minimum partial multi-cover problem (PMC).
Submodular function has many equivalent definitions. We only introduce the following one which is convenient to be used in this paper.
Definition 2.2 (submodular function). Given a ground set E, a set function ρ : 2E 7→
R is submodular if for any E ′′ ⊆ E ′ ⊆ E and E0 ⊆ E \ E ′ , we have
ρ(E ′ ∪ E0 ) − ρ(E ′ ) ≤ ρ(E ′′ ∪ E0 ) − ρ(E ′′ ).
4

(1)

Notice that a nonnegative submodular function ρ satisfies subadditivity: for any sets
X, Y ⊆ E,
ρ(X ∪ Y ) ≤ ρ(X) + ρ(Y ).
(2)
Notice that a set S ⊆ E can be indicated by its characteristic vector xS =
(x1 , . . . , xn ), where n = |E|, E = {e1 , . . . , en }, and xi = 1 if ei ∈ S and xi = 0 if
ei ∈
/ S. So, in the following, we shall use notation {0, 1}n 7→ R to refer to a set
function. The relationship between submodularity and convexity can be formulated in
terms of Lovász extension.
Definition 2.3 (Lovász extension [16]). For a set function ρ : {0, 1}n 7→ R, the Lovász
extension ρ̂ : Rn → R is defined as follows. For any vector x ∈ Rn , order elements as
ej1 , ej2 , . . . , ejn such that xj1 ≥ xj2 ≥ ... ≥ xjn , where xji is the coordinate of x indexed
by eji . Let Ei = {ej1 , ej2 , ..., eji }. The value of ρ̂ at x is
ρ̂(x) =

n−1
X
i=1

(xji − xji+1 )ρ(Ei ) + xjn ρ(En ).

(3)

The above definition implies that Lovász extension ρ̂ satisfies positive homogenous
property, that is, for any t > 0, ρ̂(tx) = tρ̂(x). The following result reveals the relationship between submodularity and convexity.
Theorem 2.4. A set function ρ is submodular if and only if its Lovász extension ρ̂ is
convex.
The following is an equivalent expression of Lovász extension in range [0, 1]n .
Theorem 2.5 ([3]). Let ρ be a set function {0, 1}n 7→ R. The Lovász extension ρ̂ of
ρ in range [0, 1]n can be equivalently expressed as
Z 1
θ
ρ̂(x) = E [ρ(x )] =
ρ(xθ )dθ,
(4)
θ∈[0,1]

0

where xθi = 1 if xi ≥ θ, otherwise xθi = 0.
In this paper, we study the SCPMC problem under the following assumptions.
(Assumption 1) The maximum covering requirement rmax = max{re : e ∈ E} has
a constant upper bound.
(Assumption 2) Since submodular cost (full) multi-cover problem is already studied in [10, 15], we only consider the partial version, that is, it is assumed that q < 1.

5

3

Approximation Algorithm for SCPMC

A natural idea to model the SCPMC problem is to use the following integer programm:
min ρ0 (x)
s.t.

X

e: e∈E

pe ye ≥ qP,

X

S: e∈S

xS ≥ re ye , for any e ∈ E

(5)

xS ∈ {0, 1} for S ∈ S
ye ∈ {0, 1} for e ∈ E
Here xS indicates whether set S is selected and ye indicates whether element e is fully
covered. The second constraint says that if ye = 1 then at least re sets containing e
must be selected and thus e is fully covered. Relaxing (5), we have the following convex
program:
min ρ̂0 (x)
s.t.

X

e: e∈E

pe ye ≥ qP,

X

S: e∈S

xS ≥ re ye , for any e ∈ E

(6)

xS ≥ 0 for S ∈ S
1 ≥ ye ≥ 0 for e ∈ E
However, based on such a program, one cannot find a good approximation. The
following example shows that the integrality gap between (5) and (6) can be arbitrarily
large, even when the profit function is a constant and the cost function is linear.
Example 3.1. Let E = {e1 , e2 }, S = {S1 , S2 , S3 } with S1 = {e1 }, S2 = {e2 }, S3 =
{e1 , e2 }, c(S1 ) = c(S2 ) = 1, c(S3 ) = M where M is a large positive number,
r(e1 ) =
P
r(e2 ) = 2, p(e1 ) = p(e2 ) = 1, q = 1/2, and the cost function ρ0 (x) = S∈S c(S)xS .
Then xS1 = xS2 = 1, xS3 = 0, ye1 = ye2 = 1/2 form a feasible solution to (6) with
objective value 2, while any integral feasible solution to (5) has cost at least M + 1.
Hence, to obtain a good approximation, we need to find another program.

3.1

Integer Program and Convex Relaxation

For an element e, an re -cover is a sub-collection A ⊆ S with |A| =Sre such that
e ∈ S for every S ∈ A. Denote by Ωe the family of all re -covers and Ω = e∈E Ωe . The
following example illustrates these concepts.
6

Example 3.2. Let E = {e1 , e2 , e3 }. S = {S1 , S2 , S3 } with S1 = {e1 , e2 }, S2 =
{e1 , e2 , e3 }, S3 = {e2 , e3 }, S4 = {e1 , e3 }, and r(e1 ) = 2, r(e2 ) = r(e3 ) = 1. For
this example, Ωe1 = {{S1 , S2 }, {S1, S4 }, {S2 , S4 }}, Ωe2 = {{S1 }, {S2 }, {S3}}, Ωe3 =
{{S2 }, {S3 }, {S4 }}, and Ω = {{S1 }, {S2 }, {S3 }, {S4 }, {S1 , S2 }, {S1, S4 }, {S2, S4 }}.
Let ρ: 2Ω → R be the function on sub-families of Ω defined by
[
ρ(Ω′ ) = ρ0 (
A)

(7)

A∈Ω′

for Ω′ ⊆ Ω. For example, ρ({{S1 }, {S1 , S2 }}) = ρ0 ({S1 , S2 }). The SCPMC problem
can be modeled as an integer program as follows.
min ρ(x)
X
s.t.
pe ye ≥ qP,
e: e∈E

X

A: A∈Ωe

xA ≥ ye , for any e ∈ E

(8)

xA ∈ {0, 1} for A ∈ Ω
ye ∈ {0, 1} for e ∈ E
Here, xA indicates whether cover A is selected and ye indicates whether element e is
fully covered. The second constraint says that if ye = 1, then at least one re -cover must
be selected and thus e is fully covered.
Example 3.3. For the example in Example 3.2, suppose pei ≡ 1 for i = 1, 2, 3 and
q = 2/3. Consider a feasible solution to (8): xA1 = xA2 = 1 for A1 = {S1 , S2 },
A2 = {S2 }, and xA = 0 for all other A ∈ Ω \ {A1, A2 }, we have ye1 = ye2 = 1 and ye3 =
0. This feasible solution to (8) has objective value ρ({A1 , A2 }) = ρ0 (S1 , S2 ), which
corresponds to a feasible solution {S1 , S2 } to SCPMC with the same cost. Conversely,
for the feasible solution {S1 , S2 } to SCPMC, it is natural to set xA1 = 1 and all other
xA to be zeros. However, this is not a feasible solution to (8). Nevertheless, one can
construct a feasible solution to (8) having the same cost by setting xA1 = xA2 = 1 and
all other xA to be zeros.
In general, for a feasible solution S ′ to SCPMC, one can construct a feasible solution
to (8) as follows: for each element e which is fully covered by S ′ , let ye = 1 and let
xAe = 1 for exactly one re -cover Ae which contains re subsets of S ′ (such Ae exists since
e is fully covered by S ′ ); all other variables are set to be zeros. Such a construction
clearly results in a feasible solution to (8) whose objective value is at most ρ0 (S ′ ) (by
the monotonicity of ρ0 ). So, (8) is indeed a characterization of the SCPMC problem.
The following lemma shows that function ρ is nonnegative, monotone nondecreasing, and submodular.
Lemma 3.4. If ρ0 is nonnegative, monotone nondecreasing, and submodular, then the
function ρ defined in (7) is also nonnegative, monotone nondecreasing, and submodular.
7

Proof. The nonnegativity and the monotonicity are obvious. To prove the submodularity, by Definition 2.2, it is sufficient to show that for any Ω′′ ⊆ Ω′ ⊆ Ω and Ω0 ⊆ Ω \ Ω′ ,
ρ(Ω′ ∪ Ω0 ) − ρ(Ω′ ) ≤ ρ(Ω′′ ∪ Ω0 ) − ρ(Ω′′ ).

(9)

S
S
′
′′
′′
′
′′
′
Denote
A∈Ω′ A
 = S′ and A∈Ω′′SA = S . Since
 Ω′′ ⊆ Ω , we have S ⊆ S . Denote
S
S1 =
A∈Ω′ ∪Ω0 A \ S and S2 =
SA∈Ω′′ ∪Ω0 A \ SS . Then S1 ⊆ S2 . Combining this
with the observation that S ′ ∪ S1 = A∈Ω′ ∪Ω0 A ⊇ A∈Ω′′ ∪Ω0 A = S ′′ ∪ S2 , we have
S ′′ ⊆ (S ′′ ∪ S2 ) \ S1 ⊆ S ′ .

(10)

It follows that
ρ(Ω′ ∪ Ω0 ) − ρ(Ω′ ) = ρ0 (S ′ ∪ S1 ) − ρ0 (S ′ )
≤ ρ0 (((S ′′ ∪ S2 ) \ S1 ) ∪ S1 ) − ρ0 ((S ′′ ∪ S2 ) \ S1 )
≤ ρ0 (((S ′′ ∪ S2 ) \ S1 ) ∪ S1 ) − ρ0 (S ′′ )
= ρ0 (S ′′ ∪ S2 ) − ρ0 (S ′′ )
= ρ(Ω′′ ∪ Ω0 ) − ρ(Ω′′ ),
where the first inequality uses submodularity of ρ0 and (10), and the second inequality
uses the monotonicity of ρ0 and (10). Inequality (9), and thus the lemma, is proved.
Remark 3.5. If ρ0 is nonnegative and submodular but is not monotone nondecreasing, then ρ is not necessarily submodular. Consider the following example. Let
S = {S1 , S2 , S3 } with ρ0 ({S1 }) = ρ0 ({S1 , S3 }) = 1 and ρ0 (S ′ ) = 0 for any other
sub-collection S ′ ⊆ S. It can be verified that ρ0 is nonnegative and submodular. Consider sub-families Ω′′ = {{S1 }} ⊆ Ω′ = {{S1 }, {S1, S2 }} and Ω0 = {{S1 , S2 , S3 }}, it
can be calculated that
ρ(Ω′ ∪ Ω0 ) − ρ(Ω′ ) = 0 − 0 = 0 > −1 = 0 − 1 = ρ(Ω′′ ∪ Ω0 ) − ρ(Ω′′ ).
So, ρ is not submodular.
Let ρ̂ be the Lovász extension of ρ. By Theorem 2.4, ρ̂ is convex. Relaxing (8), we
have the following convex program:
min ρ̂(x)
s.t.

X

e: e∈E

X

pe ye ≥ qP,

A: A∈Ωe

xA ≥ ye , for any e ∈ E

xA ≥ 0 for A ∈ Ω
1 ≥ ye ≥ 0 for e ∈ E

Lemma 3.6. Convex program (11) is polynomial-time solvable.
8

(11)

Proof. It is known that (see [7]) for a submodular function ρ, its Lov’asz extension
ρ̂(x) = ρ− (x) for any x ∈ [0, 1]|Ω| , where ρ− is the convex closure of ρ defined as follows.
For each sub-family Ω′ of Ω, denote by χΩ′ as the indicator vector of Ω′ . The convex
closure of ρ isP
the function ρ− : P
[0, 1]|Ω| 7→ R such P
that for any vector x ∈ [0, 1]|Ω| ,
−
′
ρ (x) = min{ Ω′ ⊆Ω λΩ′ ρ(Ω ) : Ω′ ⊆Ω λΩ′ χΩ′ = x, Ω′ ⊆Ω λΩ′ = 1, λΩ′ ≥ 0}. Hence
(11) can be rewritten as:
X
λΩ′ ρ(Ω′ )
min
Ω′ ⊆Ω

X

s.t.

λΩ′ = 1,

Ω′ ⊆Ω

X

e: e∈E

X

Ω′ :A∈Ω′ ⊆Ω

X

A: A∈Ωe

pe ye ≥ qP,

λΩ′ = xA , for any A ∈ Ω
xA ≥ ye , for any e ∈ E

(12)

λΩ′ ≥ 0 for Ω′ ⊆ Ω
xA ≥ 0 for A ∈ Ω
1 ≥ ye ≥ 0 for e ∈ E


Notice that this is a linear program. For each element e, |Ωe | ≤ b = maxe rfe . Since in
Assumption 1, we have assumed that rmax is upper bounded by a constant, the number
of variables in the form of xA or ye is polynomial. However, the number of variables in
the form of λΩ′ is exponential.
Consider the dual program of (12):
max a + bqP −
s.t. a +

X

A∈Ω′

X

e: e∈A

X

fe

e∈E

cA ≤ ρ(Ω′ ), for any Ω′ ⊆ Ω

(13)

de − cA ≤ 0, for any A ∈ Ω

pe b − de − fe ≤ 0, for any e ∈ E
b ≥ 0 and de , fe ≥ 0 for e ∈ E
Since both |Ω| and |E| are polynomial, to solve (13), it suffices to construct a separation
oracle for the first set of constraints.
P
Define g(Ω′ ) = ρ(Ω′ )− A∈Ω′ cA for any Ω′ ⊆ Ω. Since g is obtained by subtracting a
modular function from a submodular function, g is also a submodular function. Hence,
by finding a minimizer of g, which can be done in polynomial time, and then check
whether its g-value is at least a, we can either claim the validity of the first set of
constraints or find out a violated constraint.
9

Since (11) is a relaxation of (8), we have optcp ≤ opt, where optcp is the optimal
value of (11) and opt is the optimal integer value of (8) (which is also the optimal value
of SCPMC).

3.2

Rounding Algorithm

For a sub-collection S ′ ⊆ S, denote by C(S ′ ) the set of elements fully covered by
S . Two parameters s, t are needed which are chosen in Theorem 3.11 to guarantee the
desired ratio with high probability. The rounding algorithm consists of two phases. In
the first phase, a deterministic rounding is executed to form a sub-collection S1 . In
the second phase, a randomized rounding is executed to form a sub-collection S2 . The
output is the union of S1 and S2 .
′

Algorithm 1 Algorithm for SCP MC
Input: A SCP MC instance (E, S, r, p, q, ρ0 ), two parameters s, t satisfying 1 < t <
s ≤ 1/q, and a real positive number ε < q.
Output: A sub-collection S ′ which has total covering profit at least (q − ε)P .
1: Find an optimal solution (x∗ , y ∗ ) to (11).
2: S1 ← ∅, S2 ← ∅.
3: for all e with ye∗ ≥ 1s do
4:
For each A ∈ Ωe with x∗A ≥ bs1 , let x̂A ← 1.
5: end for
6: For all x∗A which is not rounded up to 1, set x̂A ← 0.
7: S1 ← {S : S ∈ A with x̂A = 1}.
8: If S1 has total covering profit at least (q − ε)P then output S ′ ← S1 and stop.
9: E ′ ← E − C(S1 ), q ′ ← (qP − p(C(S1 )))/P .
s
10: for i = 1 to s ln( s−t
)b do
11:
Pick θ ∈ [0, 1] randomly uniformly.
12:
For each remaining A with x∗A ≥ θ, set x̂A ← 1 and S2 ← S2 ∪ {S : S ∈ A}.
13: end for
14: Output S ′ = S2 ∪ S2 .

3.3

Approximation Analysis

Lemma 3.7. For the collection of sets S1 computed by Algorithm 1, ρ0 (S1 ) ≤ bs · optcp .
Furthermore, all elements with ye∗ ≥ 1s are fully covered by S1 .
Proof. Let x̂ be the vector defined after Line 6 of Algorithm 1, and let z be the vector
with zA = min{1, bsx∗A } for A ∈ Ω.

Recall that Lovász extension in Definition 2.3 requires an ordering of elements in a
non-increasing manner. By the definition of z and by the nonnegativity of ρ, we can
take the ordering of elements defining ρ̂(z) and ρ̂(bsx∗ ) to be the same and
ρ̂(z) ≤ ρ̂(bsx∗ ).
10

(14)

We claim that x̂A ≤ zA holds for any index A ∈ Ω. This is clearly true if x̂A = 0.
For an index A with x̂A = 1, we have x∗A ≥ 1/bs (by Line 4 of Algorithm 1), which
implies zA = 1. The claim is proved. It follows that for any θ ∈ [0, 1] and for any
θ
(recall the notation xθi defined in Theorem 2.5). Then, by the
index A ∈ Ω, x̂θA ≤ zA
monotonicity of ρ, we have
ρ(x̂θ ) ≤ ρ(z θ ).
(15)
Combining (14), (15) with the positive homogeneous property of Lovász extension,
Z 1
Z 1
θ
ρ0 (S1 ) = ρ̂(x̂) =
ρ(x̂ )dθ ≤
ρ(z θ )dθ = ρ̂(z) ≤ ρ̂(bsx∗ ) = bsρ̂(x∗ ) = bs · optcp .
0

0

Next, consider the second half of the lemma. For each element e with ye∗ ≥ 1s , by
the second constraint of (11), and by the observation that |Ωe | ≤ b, we have
max x∗A ≥ ye∗ /b ≥ 1/bs.

A∈Ωe

(16)

Hence there is at least one re -cover A ∈ Ωe with value x∗A ≥ bs1 , and thus x̂A = 1. That
is, after the deterministic rounding, at least one re -cover is chosen into S1 , and thus e
is fully covered.
Lemma 3.8. For the collection of sets S2 computed by Algorithm 1, the expected cost
s
of S2 satisfies E[ρ0 (S2 )] ≤ bs ln( s−t
)optcp .
Proof. Observe that each of the second “for” loop of Algorithm 1 is in fact a realization
of Lovász extension in Theorem 2.5 (one may refer to [3]). So the expectation of the
cost of those sets in each iteration is ρ̂(x∗ ) = optcp . Since S2 is the union of these sets,
s
s
) iterations, E[ρ0 (S2 )] ≤ bs ln( s−t
)optcp .
so after bs ln( s−t
In the following, when we say that element e is fully covered by S2 , it means that
the remaining covering requirement of e is satisfied by S2 . Using such a convention,
we
P
denote by C(S2 ) the set of elements fully covered by S2 , and let p(S2 ) = e∈C(S2 ) p(e).
Notice that S2 is in fact a random sub-collection, and thus p(S2 ) is a random value. To
be more strict, let ŷe be the random variable which takes value 1 if e is fully covered
by S2 , and takes value 0 otherwise. Then
X
p(S2 ) =
p(e)ŷe .
(17)
e∈C(S2 )

The next lemma gives an upper bound for the expected value of p(S2 ).
Lemma 3.9. For the collection of sets S2 computed by Algorithm 1, the expected profit
of S2 satisfies E[p(S2 )] ≥ tq ′ P .
P
Proof. Since E[p(S2 )] = e∈E ′ p(e)P r[ŷe = 1] and
X
X
X
p(e)ye∗ ≥ qP −
p(e)ye∗ ≥ qP −
p(e) = q ′ P,
e∈E ′

e∈C(S1 )

e∈C(S1 )

11

it suffices to prove that for each e ∈ E ′ ,
P r[ŷe = 1] ≥ tye∗ .

(18)

Notice that for each e ∈ E ′ , ye∗ ≤ 1/s. Since we have assumed t < s, so tye∗ < 1. Then,
proving (18) is equivalent to proving
P r[ŷe = 0] ≤ 1 − tye∗ .

(19)

In a “for” loop with a uniformly randomly chosen θ ∈ [0, 1], an re -cover A is chosen
into S2 if and only if x∗A ≥ θ. For an element e ∈ E ′ , it is not fully covered by those
sets chosen into S2 in this “for” loop if and only ∗if θ > max{x∗A : A ∈ Ωe }. This occurs
with probability 1 − max x∗A . Since max x∗A ≥ ybe (see (16)), we have
A∈Ωe

A∈Ωe

1−

max x∗A
A∈Ωe

ye∗
≤1− .
b

s
) iterations,
So, after bs ln( s−t
s


bs ln( s−t
−sye∗
)
s
ye∗
s
)
−sye∗ ln( s−t
P r[ŷe = 0] ≤ 1 −
=
,
≤e
b
s−t

s −sx
)
where the second inequality uses the fact that 1 − x ≤ e−x . Denote f (x) = ( s−t
and g(x) = 1 − tx. Notice that f (x) is a convex function and g(x) is a linear function.
Furthermore, f (0) = g(0), f (1/s) = g(1/s). So f (x) ≤ g(x) in interval [0, 1/s]. Since
s −sye∗
for each e ∈ E ′ , 0 ≤ ye∗ ≤ 1/s. So, ( s−t
)
≤ 1 − tye∗. Property (19) is proved, and
the lemma follows.

Remark 3.10. One may be wondering what if tq ′ P is larger than the profit of those
remaining elements which are not fully covered by S1 . This cannot happen because
after the first stage of deterministic rounding, the total profits of remaining elements
is q ′ P + (1 − q)P . Since it is required that 1 < t < s ≤ 1/q ≤ 1 + 1−q
, we have
q′
′
′
tq P < q P + (1 − q)P .
Now we will show that by choosing suitable parameters s and t, Algorithm 1 produces a feasible solution with performance ratio O(b) with high probability.
√
Theorem 3.11. Setting s = 1/q and t = 1/ q, Algorithm 1 produces a feasible

solution to SCPMC with high probability whose cost is O(b)optcp , where b = maxe rfe .
Proof. Notice that for the above s and t, we have 1 <

1
√
3

q

<t=

√1
q

< s = 1q .

The outline of the proof is as follows: we first show that the sum of the probabilities
for the following two events is a constant strictly smaller than 1; then a feasible solution
with desired performance ratio can be achieved with high probability by repeating
Algorithm 1 O(ln(n)) times. The two events are:
s
)optcp , where l =
(i) ρ0 (S2 ) > bsl ln( s−t

1−q
;
(t−1)ε

12

(ii) p(S2 ) < q ′ P .
For event (i), using Markov inequality and Lemma 3.8, we have




1
(t − 1)ε
(1 − q) + (1 − t)ε
s
optcp ≤ =
=1−
.
P r ρ0 (S2 ) > bsl ln
s−t
l
1−q
1−q

(20)

For event (ii), since q ′ > qP −(q−ε)P
= ε by Algorithm 1, q ′ P + (1 − q)P − p(S2 ) ≥ 0
P
by Remark 3.10, and E[q ′ P + (1 − q)P − p(S2 )] ≤ q ′ P + (1 − q)P − tq ′ P by Lemma
3.9, using Markov inequality,
P r [p(S2 ) ≤ q ′ P ] = P r [q ′ P + (1 − q)P − p(S2 ) ≥ (1 − q)P ]
q ′ P + (1 − q)P − tq ′ P
(1 − q) + (1 − t)ε
≤
<
.
(1 − q)P
1−q

(21)

Adding inequalities (20) and (21), the probability that either event (i) occurs or
event (ii) occurs is upper bounded by a constant which is strictly smaller that 1.
Hence, by repeating Algorithm 1 O(ln(n)) times, with a high probability, p(S2 ) ≥ q ′ P
s
and ρ0 (S2 ) ≤ bsl ln( s−t
)optcp . Combining these with Lemma 3.7, with high probability,
′
p(S ) = p(S1 ) + p(S2 ) ≥ qP and

 


b
s
′
optcp = O
optcp ,
ρ0 (S ) ≤ ρ0 (S1 ) + ρ0 (S2 ) ≤ bs 1 + l ln
s−t
ε


1
1
where the firs inequality uses (2) and the constant in big O is √q−q
)ε + (1 − q) ln( 1−1√q ) .
( √q−1
The theorem is proved.

4

Approximation Algorithm for SCPSC

As a corollary of Theorem 3.11, the minimum submodular cost partial set cover
problem (SCPSC for short, in which the covering requirement for each element is one)
admits a bicriteria randomized (ε, O( fε ))-approximation. In the following, we show that
an adaptation of our method can yield the same approximation for SCPSC even if the
submodular function ρ0 is non-monotone. The idea behind the adaptation is that in
this case, a natural constraint is sufficient (we do not need to use the more complicated
re -covers), and thus a technique similar to that in [10] dealing with non-monotone
submodular functions can be used.

13

The SCPSC problem can be modelled as the following integer program:
min ρ0 (x)
s.t.

X

e: e∈E

pe ye ≥ qP,

X

S: S∈S

xS ≥ ye , for any e ∈ E

xS ∈ {0, 1} for S ∈ S
ye ∈ {0, 1} for e ∈ E,
Its relaxation is a convex program:
min ρˆ0 (x)
s.t.

X

e: e∈E

X

pe ye ≥ qP,

S: S∈S

xS ≥ ye , for any e ∈ E

(22)

xS ≥ 0 for S ∈ S
1 ≥ ye ≥ 0 for e ∈ E
Notice that since we can use ρ0 as objective function here, the convexity follows directly
from the submodularity of ρ0 . While for program (11), its convexity is guaranteed by
Lemma 3.4, which is no longer true if ρ0 is non-monotone (see Remark 3.5).
Define a new function γ by γ(S ′ ) = min{ρ0 (S ′′ ) : S ′ ⊆ S ′′ ⊆ S}. Then γ is a
nonnegative monotone nondecreasing submodular function (see [10]). For any subcollection S ′ ⊆ S, the value of γ(S ′ ) can be determined in polynomial time by an
algorithm for submodualr function minimization. Let S0′ be the minimizer, that is,
S ′ ⊆ S0′ ⊆ S and ρ(S0′ ) = γ(S ′ ). It should be noticed that S0′ can fully cover all those
elements which are fully covered by S ′ (since S ′ ⊆ S0′ ).
Our algorithm for SCPSC is similar to Algorithm 1 with the following two differences. First, replace convex program (11) by (22). Second, having obtained S1 ,
compute (S1 )0 and replace S1 by (S1 )0 in the remaining part of Algorithm 1.

Notice that in the analysis, monotonicity is used only in Lemma 3.7. So, to obtain
the desired result, we only need to prove the following lemma.
Lemma 4.1. ρ((S1 )0 ) ≤ bs · optcp .

Proof. Let x̂ be the indicator vector of S1 . By the monotonicity of γ, the Lovász
extension γ̂ is also monotone nondecreasing. Hence it follows from x̂ ≤ bsx∗ that
γ̂(x̂) ≤ γ̂(bsx∗ ).

(23)

For any sub-collection S ′ ⊆ S, by Definition 2.3, γ(S ′ ) ≤ ρ(S ′ ). By the definition of
Lovász extension in Definition 2.3, we have
γ̂(x) ≤ ρ̂(x) holds for any vector x ∈ [0, 1]|S|.
14

(24)

Combining (23), (24) with the positive homogeneous property of Lovász extension,
ρ((S1 )0 ) = γ(S1 ) = γ̂(x̂) ≤ γ̂(bsx∗ ) = bsγ̂(x∗ ) ≤ bsρ̂(x∗ ) = bs · optcp .
The lemma is proved.
From the above argument, we have the following result.
Theorem 4.2. For any nonnegative submodular function, the SCP SC problem has a
bicriteria randomized (ε, O( fε ))-approximation with high probability.

5

Conclusion

By introducing a novel convex program describing the minimum submodular cost
partial multi-cover problem (SCPMC), we give a randomized (ε, O( εb ))-approximation

algorithm for SCPMC, where b = maxe rfe . Since PMC is a special case of SCPMC, the
PMC problem also has a bicriteria randomized (ε, O( εb ))-approximation algorithm with
a high probability. We show that in the case when the covering requirement for each
element is one, monotonicity requirement can be dropped off from the cost function. It
should be noticed that if we only care about an expected result, then we may obtain a
s
)opt
randomized algorithm producing a sub-collection S ′ with E[ρ0 (S ′ )] ≤ bs(1 + ln s−t
′
and E[p(S )] ≥ qP . This can be achieved by modifying (q − ε)P in Line 8 of Algorithm
1 into qP .
One question is can one obtain the same result for SCPMC without monotonicity
requirement? Another question is what if rmax is not upper bounded by a constant?

Acknowledgements
This research is supported by NSFC (11531011, 61222201).

References
[1] Bar-Yehuda R (2001) Using homogeneous weights for approximating the partial
cover problem. Journal of Algorithms, 39: 137–144.
[2] Berman P, DasGupta B, Sontag E (2007) Randomized approximation algorithms
for set multicover problems with applications to reverse engineering of protein and
gene networks. Discrete Applied Mathematics, 155 (6-7): 733–749.
[3] Chekuri C, Ene A (2011) Submodular cost allocation problem and applications.
International Colloquium on Automata, Languages, and Programming, 354–366.

15

[4] Dinur I, Steurer D (2014) Analytical approach to parallel repetition. STOC2014,
624–633.
[5] Chvatal V (1979) A greedy heuristic for the set covering problem, Mathematics of
Operations Research 4(3): 233–235.
[6] Dobson G (1982) Worst-case analysis of greedy heuristics for integer program with
nonnegatice data. Mathematics of Operations Research 7: 515–531.
[7] Dughmi S (2009) Submodular functions: extensions, distributions, and algorithms.
A survey. arXiv:0912.0322 [], 2009.
[8] Gandhi R, Khuller S, Srinivasan A (2004) Approximation algorithms for partial
covering problems. Journal of Algorithms, 53(1): 55–84.
[9] Hochbaum DS (1982) Approximation algorithms for the set covering and vertex
cover problems. SIAM Journal on Computing 11: 555–556.
[10] Iwata S, Nagano K (2009) Submodular function minimization under covering constraints. FOCS2009, 671–680.
[11] Johnson D, (1974) Approximation algorithms for combinatorial problems, Journal
of Computer System Sciences 9:256–278.
[12] Kearns M (1990) The Computational Complexity of Machine Learning. MIT Press,
Cambridge, MA.
[13] Khot S, Regev O (2008) Vertex cover might be hard to approximate to within
2 − ε. Journal of Computer and System Sciences, 74(3) 335–349.
[14] Konemann J, Parekh O, Segev D (2011) A uinifed approach to approximating
partial covering problems. Algorithmica, 59: 489–509.
[15] Koufogiannakis C, Young N (2013) Greedy ∆-approximation algorithm for covering with arbitrary constraints and submodular cost. Algorithmica, 66(1): 113–152.
[16] Lovász L (1983) Submodular functions and convexity. Mathematical Programming
The State of the Art, 235–257.
[17] Lovász L (1975) On the ratio of the optimal integral and fractional covers. Discrete
Mathematics 13: 383–390.
[18] Rajagopalan S, Vazirani V (1998) Primal-dual RNC approximation algorithms for
set cover and covering integer programs. SIAM Journal on Computing 28: 525–540.
[19] Ran Y, Zhang Z, Du H, Zhu Y (2016) Approximation algorithm for partial positive
influence problem in social network. Journal of Combinatorial Optimization, DOI
10.1007/s10878-016-0005-0: 1–12.
[20] Ran Y, Shi Y, Zhang Z (2016) Local ratio method on partial set multi-cover.
Journal of Combinatorial Optimization, DOI 10.1007/s10878-016-0066-0.
16

[21] Slavı́k P (1997) Improved performance of the greedy algorithm for partial cover.
Information Processing Letters, 64(5): 251–254.

17

