arXiv:1704.01652v1 [cs.LG] 5 Apr 2017

Greed Is Good: Near-Optimal Submodular
Maximization via Greedy Optimization
Moran Feldman1 , Christopher Harshaw2 , and Amin Karbasi3
1

Department of Mathematics and Computer Science, Open University of Israel
2
Department of Computer Science, Yale University
3
Department of Electrical Engineering, Yale University

April 7, 2017
Abstract
It is known that greedy methods perform well for maximizing monotone submodular
functions. At the same time, such methods perform poorly in the face of non-monotonicity.
In this paper,
√ we show—arguably, surprisingly—that invoking the classical greedy algorithm O( k)-times leads to the (currently) fastest deterministic algorithm, called R EPEATED G REEDY, for maximizing a general submodular function
subject to k-independent system
√
√
constraints. R EPEATED G REEDY achieves (1+O(1/ k))k approximation using O(nr k)
function evaluations (here, n and r denote the size of the ground set and the maximum size
of a feasible solution, respectively). We then show that by a careful sampling procedure,
we can run the greedy algorithm only once and obtain the (currently) fastest randomized
algorithm, called S AMPLE G REEDY, for maximizing a submodular function subject to kextendible system constraints (a subclass of k-independent system constrains). S AMPLE G REEDY achieves (k + 3)-approximation with only O(nr/k) function evaluations. Finally,
we derive an almost matching lower bound, and show that no polynomial time algorithm can
have an approximation ratio smaller than k + 1/2 − ε. To further support our theoretical results, we compare the performance of R EPEATED G REEDY and S AMPLE G REEDY with prior
art in a concrete application (movie recommendation). We consistently observe that while
S AMPLE G REEDY achieves practically the same utility as the best baseline, it performs at
least two orders of magnitude faster.
Keywords: Submodular maximization, k-systems, k-extendible systems, approximation algorithms

1

1

Introduction

Submodular functions [Edmonds, 1971, Fujishige, 2005], originated in combinatorial optimization and operations research, exhibit a natural diminishing returns property common in
many well known objectives: the marginal benefit of any given element decreases as more and
more elements are selected. As a result, submodular optimization has found numerous applications in machine learning, including viral marketing [Kempe et al., 2003], network monitoring
[Leskovec et al., 2007, Gomez Rodriguez et al., 2010], sensor placement and information gathering [Guestrin et al., 2005], news article recommendation [El-Arini et al., 2009], nonparametric
learning [Reed and Ghahramani, 2013], document and corpus summarization [Lin and Bilmes,
2011, Kirchhoff and Bilmes, 2014, Sipos et al., 2012], data summarization [Mirzasoleiman
et al., 2013], crowd teaching [Singla et al., 2014], and MAP inference of determinental point
process [Gillenwater et al., 2012]. The usefulness of submodular optimization in these settings
stems from the fact that many such problems can be reduced to the problem of maximizing a
submodular function subject to feasibility constraints, such as cardinality, knapsack, matroid or
intersection of matroids constraints.
In this paper, we consider the maximization of submodular functions subject to two important classes of constraints known as k-system and k-extendible system constraints. The class of
k-system constraints is a very general class of constraints capturing, for example, any constraint
which can be represented as the intersection of multiple matroid and matching constraints. The
study of the maximization of monotone submodular functions subject to a k-system constraint
goes back to the work of Fisher et al. [1978], who showed that the natural greedy algorithm
achieves an approximation ratio of 1/(k + 1) for this problem (k is a parameter of the k-system
constraint measuring, intuitively, its complexity). In contrast, results for the maximization of
non-monotone submodular functions subject to a k-system constraint were only obtained much
more recently. Specifically, Gupta et al. [2010] showed that, by repeatedly executing the greedy
algorithm and an algorithm for unconstrained submodular maximization, one can maximize a
non-monotone submodular function subject to a k-system constraint up to an approximation
ratio of roughly 3k using a time complexity of O(nrk)1 . This was recently improved by Mirzasoleiman et al. [2016], who showed that the approximation ratio obtained by the above approach
is in fact roughly 2k.
The algorithms we describe in this paper improve over the above mentioned results both
in terms of the approximation ratio and in terms of the time complexity. Our first result is
a deterministic√algorithm, called R EPEATED G REEDY, which obtains an approximation ratio
submodular function subject
of (1 + O(1/ k))k for the maximization of a non-monotone √
to a k-system constraint using a time complexity of only O(nr k). R EPEATED G REEDY is
structurally very similar to the algorithm of Gupta et al. [2010] and Mirzasoleiman et al. [2016].
However, thanks to a tighter analysis, it needs to execute the greedy algorithm and the algorithm
for unconstrained submodular maximization much less often, which yields its improvement in
the time complexity.
Our second result is a randomized algorithm, called S AMPLE G REEDY, which manages
to further push the approximation ratio and time complexity to (k + 1)2 /k ≤ k + 3 and
O(n + nr/k), respectively. However, it does so at a cost. Specifically, S AMPLE G REEDY
applies only to a subclass of k-system constraints known as k-extendible system constraints.
We note, however, that the class of k-extendible constraints is still general enough to capture,
among others, any constraint that can be represented as the intersection of multiple matroid
and matching constraints. Interestingly, when the objective function is also monotone or linear
1 Here, and throughout the paper, n represents the size of the ground set of the submodular function and r represents
the maximum size of any set satisfying the constraint.

2

Table 1: Summary of Results for Non-monotone Submodular Objectives
Approximation Ratio
S AMPLE G REEDY (randomized)
R EPEATED G REEDY (deterministic)
Mirzasoleiman et al. [2016]
Gupta et al. [2010]
Inapproximability

2

(k + 1) /k ≤ k + 3
√
k + O( k)
≈ 2k
≈ 3k
(1 − e−k )−1 − ε ≥ k + 1/2 − ε

Time Complexity

O(n + nr/k)
√
O(nr k)
O(nrk)
O(nrk)
−

the approximation ratio of S AMPLE G REEDY improves to k + 1 and k, respectively,2 which
matches the best known approximation ratios for the maximization of such functions subject to
a k-extendible system constraint [Fisher et al., 1978, Jenkyns, 1976, Mestre, 2006]. Previously,
these ratio were obtained using the greedy algorithm whose time complexity is O(nr). Hence,
our algorithm also improves over the state of the art algorithm for maximization of monotone
submodular and linear functions subject to a k-extendible system constraint in terms of the time
complexity.
We complement our algorithmic results with two inapproximability results showing that
the approximation ratios obtained by our second algorithm are almost tight. Previously, it was
known that no polynomial time algorithm can have an approximation ratio of k − ε (for any
constant ε > 0) for the problem of maximizing a linear function subject to a k-system constraint [Badanidiyuru and Vondrák, 2014]. We show that this result extends also to k-extendible
systems, i.e., that no polynomial time algorithm can have an approximation ratio of k −  for the
problem of maximizing a linear function subject to a k-extendible system constraint. Moreover,
for monotone submodular functions we manage to get a slightly stronger inapproximability result. Namely, we show that no polynomial time algorithm can have an approximation ratio
of 1/(1 − e−k ) − ε ≤ k + 1/2 − ε for the problem of maximizing a monotone submodular
function subject to a k-extendible system constraint. Note that the gap between the approximation ratio obtained by S AMPLE G REEDY (namely, (k + 3)) and the inapproximability result
(namely, (k + 1/2 − ε)) is very small. A short summary of all the results discussed above for
non-monotone submodular objectives can be found in Table 1.
Finally, we compare the performance of R EPEATED G REEDY and S AMPLE G REEDY against
FATNOM, the current state of the art algorithm introduced by Mirzasoleiman et al. [2016].
We test these algorithms on a movie recommendation problem using the MovieLens dataset,
which consists of over 20 million ratings of 27,000 movies by 138,000 users. We find that
our algorithms provide solution sets of similar quality as FANTOM while running orders of
magnitude faster. In fact, we observe that taking the best solution found by several independent
executions of S AMPLE G REEDY clearly yields the best trade-off between solution quality and
computational cost. Moreover, our experimental results indicate that our faster algorithms could
be applied to large scale problems previously intractable for other methods.
Organization: Section 2 contains a brief summary of additional related work. A formal presentation of our main results and some necessary preliminaries are given in Section 3. Then, in
Sections 4 and 5 we present and analyze our deterministic and randomized approximation algorithms, respectively. The above mentioned experimental results comparing our algorithms with
previously known algorithms can be found in Section 6. Finally, our hardness results appear in
2 The

improvement for linear objectives requires a minor modification of the algorithm.

3

Appendix A.

2

Related Works

Submodular maximization has been studied with respect to a few special cases of k-extendible
system constraints. Lee et al. [2010] described a local search algorithm achieving an approximation ratio of k+ for maximizing a monotone submodular function subject to the intersection
of any k matroid constraints, and explained how to use multiple executions of this algorithm to
1
get an approximation ratio of k + 1 + k+1
+ ε for this problem even when the objective function
is non-monotone. Later, Feldman et al. [2011b] showed, via a different analysis, that the same
local search algorithm can also be used to get essentially the same results for the maximization of a submodular function subject to a subclass of k-extendible system constraints known
as k-exchange system constraints (this class of constraints captures the intersection of multiple
matching and strongly orderable matroid constraints). For k ≥ 4, the approximation ratio of
[Feldman et al., 2011b] for the case of a monotone submodular objective was later improved by
Ward [2012] to (k + 3)/2 + ε.
An even more special case of k-extendible systems are the simple matroid constraints. In
their classical work, Nemhauser et al. [1978] showed that the natural greedy algorithm gives an
approximation ratio of 1 − 1/e for maximizing a monotone submodular function subject to a
uniform matroid constraint (also known as cardinality constraint), and Călinescu et al. [2011]
later obtained the same approximation ratio for general matroid constraints using the Continuous Greedy algorithm. Moreover, both results are known to be optimal [Nemhauser and Wolsey,
1978]. However, optimization guarantees for non-montone submodular maximization are much
less well understood. After a long series of works [Vondrák, 2013, Gharan and Vondrák, 2011,
Feldman et al., 2011a, Ene and Nguyen, 2016], the current best approximation ratio for maximizing a non-monotone submodular function subject to a matroid constraint is 0.385 [Buchbinder and Feldman, 2016a]. In contrast, the state of the art inapproximability result for this
problem is 0.478 [Gharan and Vondrák, 2011].
Recently, there has also been a lot of interest in developing fast algorithms for maximizing submodular functions. Badanidiyuru and Vondrák [2014] described algorithms that achieve
an approximation ratio of 1 − 1/e − ε for maximizing a monotone submodular function subject to uniform and general matroid constraints using time complexities of Oε (n log k) and
Oε (nr log2 n), respectively (Oε suppresses a polynomial dependence on ε).3 For uniform matroid constraints, Mirzasoleiman et al. [2015] showed that one can completely get rid of the
dependence on r, and get an algorithm with the same approximation ratio whose time complexity is only Oε (n). Independently, Buchbinder et al. [2015b] showed that a technique similar
to Mirzasoleiman et al. [2015] can be used to get also (e−1 − ε)-approximation for maximizing
a non-monotone submodular function subject to a cardinality constraint using a time complexity
of Oε (n). Buchbinder et al. [2015b] also described a different (1 − 1/e − ε)-approximation
algorithm for maximizing a monotone submodular function
to a general matroid con√ subject
2
2
r
log
n)
for general matroids, and
straint. The time complexity
of
this
algorithm
is
O
(r
+
n
ε
√
it can be improved to Oε (r n log n + n log2 n) for generalized partition matroids.
3 Badanidiyuru and Vondrák [2014] also describe a fast algorithm for maximizing a monotone submodular function
subject to a knapsack constraint. However, the time complexity of this algorithm is exponential in 1/ε, and thus, its
contribution is mostly theoretical.

4

3

Preliminaries and Main Results

In this section we formally describe our main results. However, before we can do that, we first
need to present some basic definitions and other preliminaries.

3.1

Preliminaries

For a set A and element e, we often write the union A∪{e} as A+e for simplicity. Additionally,
we say that f is a real-valued set function with ground set N if f assigns a real number to each
subset of N . We are now ready to introduce the class of submodular functions.
Definition 1. Let N be a finite set. A real-valued set function f : 2N → R is submodular if,
for all X, Y ⊆ N ,
f (X) + f (Y ) ≥ f (X ∩ Y ) + f (X ∪ Y ) .
(1)
Equivalently, for all A ⊆ B ⊆ N and e ∈ N \ B,
f (A + e) − f (A) ≥ f (B + e) − f (B) .

(2)

While definitions (1) and (2) are equivalent, the latter one, which is known as the diminishing returns property, tends to be more helpful and intuitive in most situations. Indeed, the fact
that submodular functions capture the notion of diminishing returns is one of the key reasons for
the usefulness of submodular maximization in combinatorial optimization and machine learning. Due to the importance and usefulness of the diminishing returns property, it is convenient
to define, for every e ∈ N and S ⊆ N , ∆f (e|S) := f (S + e) − f (S). In this paper we only
consider the maximization of submodular functions which are non-negative (i.e., f (A) ≥ 0 for
all A ⊆ N ).4
As explained above, we consider submodular maximization subject to two kinds of constraints: k-system and k-extendible system constraints. Both kinds can be cast as special cases
of a more general class of constraints known as independence system constraints. Formally, an
independence system is a pair (N , I), where N is a finite set and I is a non-empty subset of
2N having the property that A ⊆ B ⊆ N and B ∈ I imply together A ∈ I.
Let us now define some standard terminology related to independence systems. The sets
of I are called the independent sets of the independence system. Additionally, an independent
set B contained in a subset X of the ground set N is a base of X if no other independent set
A ⊆ X strictly contains B. Using this terminology we can now give the formal definition of
k-systems.
Definition 2. An independence system (N , I) is called a k-system if for every set X ⊆ N the
sizes of the bases of X differ by at most a factor of k. More formally, |B1 |/|B2 | ≤ k for every
two bases B1 , B2 of X.
An important special case of k-systems are the k-extendible systems, which were first introduced by Mestre [2006]. We say that an independent set B is an extension of an independent
set A if B strictly contains A.
Definition 3. An independence system (N , I) is k-extendible if for every independent set A ∈
I, an extension B of this set and an element e ∈
/ A obeying A ∪ {e} ∈ I there must exist a
subset Y ⊆ B \ A with |Y | ≤ k such that B \ Y ∪ {e} ∈ I.
4 See [Feige et al., 2011] for an explanation why submodular functions that can take negative values cannot be
maximized even approximately.

5

Intuitively, an independence system is k-extendible if adding an element e to an independent
set A requires the removal of at most k other elements in order to keep the resulting set independent. As is shown by Mestre [2006], the intersection of k matroids defined on a common
ground set is always a k-extendible system. The converse is not generally true (except in the
case of k = 1, since every 1-system is a matroid).

3.2

Main Contributions

Our main contributions in this paper are two efficient algorithms for submodular maximization:
one deterministic and one randomized. The following theorem formally describes the properties
of our randomized algorithm. Recall that n is the size of the ground set and r is the size of the
maximal feasible set.
Theorem 1. Let f : 2N → R≥0 be a non-negative submodular function, and let (N , I) be
a k-extendible system. Then, there exists an O(n + nr/k) time algorithm for maximizing f
2
. Moreover, if the function f is also
over (N , I) whose approximation ratio is at least (k+1)
k
monotone or linear, then the approximation ratio of the algorithm improves to k + 1 and k,
respectively (in the case of a linear objective, the improvement requires a minor modification of
the algorithm).
Our deterministic algorithm uses an algorithm for unconstrained submodular maximization
as a subroutine, and its properties depend on the exact properties of this subroutine. Let us
denote by α the approximation ratio of this subroutine and by T (n) its time complexity given
a ground set of size n. Then, as long as the subroutine is deterministic, our algorithm has the
following properties.
Theorem 2. Let f : 2N → R≥0 be a non-negative submodular
function, and let (N , I) be a
√
k-system. Then, there exists a deterministic O((nr + T (r)) k) time
for maximizing
√ algorithm
√
f over (N , I) whose approximation ratio is at least k + 1 + α2
k + 2 + α2 + O(1/ k).
Buchbinder et al. [2015a] provide a deterministic linear-time algorithm for unconstrained
submodular maximization having an approximation ratio of 3. Using this deterministic algorithm as the subroutine,
the approximation
ratio of the algorithm guaranteed √
by Theorem 2
√
√
becomes k + 25 k + 72 + O(1/ k) and its time complexity becomes O(nr k). We note
that Buchbinder and Feldman [2016b] recently came up with a deterministic algorithm for unconstrained submodular maximization having an optimal approximation ratio of 2. Using this
algorithm instead of the deterministic algorithm of Buchbinder et al. [2015a] could marginally
improve the approximation ratio guaranteed by Theorem 2. However, the algorithm of Buchbinder and Feldman [2016a] has a quadratic time complexity, and thus, it is less practical. It is
also worth noting that Buchbinder et al. [2015a] also describe a randomized linear-time algorithm for unconstrained submodular maximization which again achieves the optimal approximation ratio of
√ 2. It turns out√that one can get a randomized algorithm whose approximation
ratio is k + 2 k + 3 + O(1/ k) by plugging the randomized algorithm of [Buchbinder et al.,
2015a] as a subroutine into the algorithm guaranteed by Theorem 2. However, the obtained randomized algorithm is only useful for the rare case of a k-system constraint which is not also a
k-extendible system constraint since Theorem 1 already provides a randomized algorithm with
a better guarantee for constraints of the later kind.
We end this section with our inapproximability results for maximizing linear and submodular functions over k-extendible systems. Recall that these inapproximability results nearly
match the approximation ratio of the algorithm given by Theorem 1.

6

Theorem 3. There is no polynomial time algorithm for maximizing a linear function over a
k-extendible system that achieves an approximation ratio of k − ε for any constant ε > 0.
Theorem 4. There is no polynomial time algorithm for maximizing a non-negative monotone
submodular function over a k-extendible system that achieves an approximation ratio of (1 −
e−1/k )−1 − ε for any constant ε > 0.
We note that the inapproximability results given by the last two theorems apply also to a
fractional relaxation of the corresponding problems known as the multilinear relaxation. This
observation has two implications. The first of these implications is that even if we were willing
to settle for a fractional solution, still we could not get a better than (1/(1−e−k ))-approximation
for maximizing a monotone submodular function subject to a k-extendible system constraint.
Interestingly, this approximation ratio can in fact be reached in the fractional case even for
k-system constraints using the well known (computationally heavy) Continuous Greedy algorithm of Călinescu et al. [2011]. Thus, we get the second implication of the above observation,
which is that further improving our inapproximability results requires the use of new techniques
since the current technique cannot lead to different results for the fractional and non-fractional
problems.

4

Repeated Greedy: An Efficient Deterministic Algorithm

In this section, we present and analyze the deterministic algorithm for maximizing a submodular
function f subject to a k-system constraint whose existence is guaranteed by Theorem 2. Our
algorithm works in iterations, and in each iteration it makes three operations: executing the
greedy algorithm to produce a feasible set, executing a deterministic unconstrained submodular
maximization algorithm on the output set of the greedy algorithm to produce a second feasible
set, and removing the elements of the set produced by the greedy algorithm from the ground
set. After the algorithm makes ` iterations of this kind, where ` is a parameter to be determined
later, the algorithm terminates and outputs the best set among all the feasible sets encountered
during its iterations. A more formal statement of this algorithm is given as Algorithm 1.
Algorithm 1: Repeated Greedy(N , f, I, `)

5

Let N1 ← N .
for i = 1 to ` do
Let Si be the output of the greedy algorithm given Ni as the ground set, f as the
objective and I as the constraint.
Let Si0 be the output of a deterministic algorithm for unconstrained submodular
maximization given Si as the ground set and f as the objective.
Let Ni+1 ← Ni \ Si .

6

return the set T maximizing f among the sets {Si , Si0 }`i=1 .

1
2
3

4

Observation 1. The set T returned by Algorithm 1 is independent.
Proof. For every 1 ≤ i ≤ `, the set Si is independent because the greedy algorithm returns an
independent set. Moreover, the set Si0 is also independent since (N , I) is an independence system and the algorithm for unconstrained maximization must return a subset of its independent
ground set Si . The observation now follows since T is chosen as one of these sets.

7

We now begin the analysis of the approximation ratio of Algorithm 1. Let OPT be an
independent set of (N , I) maximizing f , and let α be the approximation ratio of the unconstrained submodular maximization algorithm used by Algorithm 1. The analysis is based on
three lemmata. The first of these lemmata states properties of the sets Si and Si0 which follow
immediately from the definition of α and known results about the greedy algorithm.
Lemma 1. For every 1 ≤ i ≤ `, f (Si ) ≥

1
0
k+1 f (Si ∪(OPT∩Ni )) and f (Si )

≥ f (Si ∩OPT)/α.

Proof. The set Si is the output of the greedy algorithm when executed on the k-system obtained
by restricting (N , I) to the ground set Ni . Note that OPT ∩ Ni is an independent set of this
1
f (Si ∪ (OPT ∩ Ni )) is a direct application of
k-system. Thus, the inequality f (Si ) ≥ k+1
Lemma 3.2 of [Gupta et al. [2010]] which states that the sets S obtained by running greedy
1
with a k-system constraint must obey f (S) ≥ k+1
f (S ∪ C) for all independent sets C of the
k-system.
Let us now explain why the second inequality of the lemma holds. Suppose that OPTi is the
subset of Si maximizing f . Then,
f (Si0 ) ≥ f (OPTi )/α ≥ f (Si ∩ OPT)/α ,
where the first inequality follows since α is the approximation ratio of the algorithm used for
unconstrained submodular maximization, and the second inequality follows from the definition
of OPTi .
The next lemma shows that the average value of the union between a set from {Si }`i=1 and
OPT must be quite large. Intuitively this follows from the fact that these sets are disjoint, and
thus, every “bad” element which decreases the value of OPT can appear only in one of them.
Lemma 2.

P̀

f (Si ∪ OPT) ≥ (` − 1)f (OPT).

i=1

Proof. The proof is based on the following known result.
Claim 1 (Lemma 2.2 of Buchbinder et al. [2014]). Let g : 2N → R≥0 be non-negative and
submodular, and let S a random subset of N where each element appears with probability at
most p (not necessarily independently). Then, E[g(S)] ≥ (1 − p)g(∅).
Using this claim we can now prove the lemma as follows. Let S be a random set which
is equal to every one of the sets {Si }`i=1 with probability 1` . Since these sets are disjoint,
every element of N belongs to S with probability at most p = 1r . Additionally, let us define
g : 2N → R≥0 as g(T ) = f (T ∪OPT) for every T ⊆ N . One can observe that g is non-negative
and submodular, and thus, by Claim 1,
`

1X
f (Si ∪ OPT) = E[f (S ∪ OPT)] = E[g(S)] ≥ (1 − p)g(∅) =
` i=1



1
1−
f (OPT) .
`

The lemma now follows by multiplying both sides of the last inequality by `.
The final lemma we need is the following basic fact about submodular functions.
Lemma 3. Suppose f is a non-negative submodular function over ground set N . For every
three sets A, B, C ⊆ N , f (A ∪ (B ∩ C)) + f (B \ C) ≥ f (A ∪ B).

8

Proof. Observe that
f (A ∪ (B ∩ C)) + f (B \ C) ≥ f (A ∪ (B ∩ C) ∪ (B \ C)) + f ((A ∪ (B ∩ C)) ∩ (B \ C))
≥ f (A ∪ (B ∩ C) ∪ (B \ C)) = f (A ∪ B) ,
where the first inequality follows from the submodularity of f , and the second inequality follows
from its non-negativity.
Having the above three lemmata, we are now ready to prove Theorem 2.
Proof of Theorem 2. Observe that, for every 1 ≤ i ≤ `, we have

i−1
OPT \ Ni = OPT ∩ (N \ Ni ) = OPT ∩ ∪j=1
Si = ∪i−1
j=1 (OPT ∩ Sj )

(3)

where the first equality holds because OPT ⊆ N and the second equality follows from the
removal of Si from the ground set in each iteration of Algorithm 1. Using the previous lemmata
and this observation, we get
(` − 1)f (OPT) ≤

`
X

f (Si ∪ OPT)

(Lemma 2)

i=1

≤

`
X

f (Si ∪ (OPT ∩ Ni )) +

`
X

f (Si ∪ (OPT ∩ Ni )) +

i=1

≤

`
X

f (OPT \ Ni )

(Lemma 3)

i=1

i=1

=

`
X

`
X


i−1
f ∪j=1
(OPT ∩ Sj )

(Equality (3))

i=1

f (Si ∪ (OPT ∩ Ni )) +

i=1

≤ (k + 1)

f (OPT ∩ Sj )

(submodularity)

i=1 j=1
`
X

f (Si ) + α

i=1

≤ (k + 1)

` X
i−1
X

`
X
i=1

` X
i−1
X

f (Sj0 )

(Lemma 1)

i=1 j=1

f (T ) + α

` X
i−1
X

f (T )

(T ’s definition)

i=1 j=1

= [(k + 1)` + α`(` − 1)/2] f (T ) .
Dividing the last inequality by (k + 1)` + α`(` − 1)/2, we get
f (T ) ≥

1 − 1`
`−1
f (OPT) =
α
α
(k + 1)` + 2 `(` − 1)
k + 2`+1−

α
2

f (OPT) .

(4)
k+ α `+1− α

2
2
The last inequality shows that the approximation ratio of Algorithm 1 is at most
.
1− 1`
To prove thetheorem
it
remains
to
show
that,
for
an
appropriate
choice
of
`,
this
ratio
is
at
most
√
√
√
k + 1 + α2
k + 2 + α2 + O(1/ k). It turns out that the right value of ` for us is d ke.
Plugging this value into Inequality (4) we get that the approximation ratio of Algorithm 1 is at
most
√
√
k + α2 ` + 1 − α2
k + α2 ( k + 1) + 1 − α2
k + α2 k + 1
≤
=
1 − 1`
1 − √1k
1 − √1k

α √
α 4+α
≤k+ 1+
k+2+ + √
,
2
2
k

9

where the last inequality holds because for k ≥ 4 it holds that




α √
α 4+α
1
α√
4+α 4+α
k+ 1+
k+2+ + √
1− √
=k+
k+1+ √ −
2
2
2
k
k
k
2 k
α√
≥k+
k+1 .
2

5

Sample Greedy: An Efficient Randomized Algorithm

In this section, we present and analyze a randomized algorithm for maximizing a submodular function f subject to a k-extendible system constraint. Our algorithm is very simple: it
first samples elements from N , and then runs the greedy algorithm on the sampled set. This
algorithm is outlined as Algorithm 2.
Algorithm 3:
Equivalent Algorithm(N , f, I, k)
Algorithm 2:
Sample Greedy(N , f, I, k)
1
2
3
4

Let N 0 ← ∅ and S ← ∅.
for u ∈ N do
with probability (k + 1)−1 do
Add u to N 0 .

7

while there exists u ∈ N 0 such that
S + u ∈ I and ∆f (u|S) > 0 do
Let u ∈ N 0 be the element of
this kind maximizing ∆f (u|S).
Add u to S.

8

return S.

5

6

1
2

3

4
5
6

7
8
9

Let N 0 ← N , S ← ∅ and O ← OP T .
while there exists an element u ∈ N 0 such
that S + u ∈ I and ∆f (u|S) > 0 do
Let u ∈ N 0 be the element of this kind
maximizing ∆f (u|S), and let Su ← S.
with probability (k + 1)−1 do
Add u to S and O.
Let Ou ⊆ O \ S be the smallest set
such that O \ Ou ∈ I.
otherwise
if u ∈ O then Let Ou ← {u}.
else Let Ou ← ∅.
Remove the elements of Ou from O.
Remove u from N 0 .

10
11
12

return S.

To better analyze Algorithm 2, we introduce an auxiliary algorithm given as Algorithm 3.
It is not difficult to see that both algorithms have identical output distributions. The sampling
of elements in Algorithm 2 is independent of the greedy maximization, so interchanging these
two steps does not affect the output distribution. Moreover, the variables Su , O and Ou in
Algorithm 3 do not affect the output S (and in fact, appear only for analysis purposes). Thus, the
two algorithms are equivalent, and any approximation guarantee we can prove for Algorithm 3
immediately carries over to Algorithm 2.
Next, we are going to analyze Algorithm 3. However, before doing it, let us intuitively
explain the roles of the sets S, Su , O and Ou in this algorithm. We say that Algorithm 3
considers an element u in some iteration if u is the element chosen as maximizing ∆f (u|S) at
the beginning of this iteration. Note that an element is considered at most once, and perhaps
not at all. As in Algorithm 2, S is the current solution. Likewise, Su is the current solution
S at the beginning of the iteration in which Algorithm 3 considers u. The set O maintained in
Algorithm 3 is an independent set which starts as OPT and changes over time, while preserving
three properties:
P1 O is an independent set.
10

P2 Every element of S is an element of O.
P3 Every element of O \ S is an element not yet considered by Algorithm 3.
Because these properties need to be maintained throughout the excecution, some elements may
be removed from O in every given iteration. The set Ou is simply the set of elements removed
from O in the iteration in which u is considered. Note that Ou and Su are random sets, and
Algorithm 3 defines values for them if it considers u at some point. In the analysis below we
assume that both Su and Ou are empty if u is not considered by Algorithm 3 (which means that
Algorithm 3 does not explicitly set values for them).
We now explain how the algorithm manages to maintain the above mentioned properties of
O. Let us begin with properties P1 and P2. Clearly the removal of elements from O that do
not belong to S cannot violate these properties, thus, we only need to consider the case that the
algorithm adds an element u to S in some iteration. To maintain P2, u is also added to O. On
the one hand, O + u might not be independent, and thus, the addition of u to O might violate
P1. However, since O is an extension of S by P2, S + u is independent by the choice of u and
(N , I) is a k-extendible system, the algorithm is able to choose a set Ou ⊆ O \ S of size at
most k whose removal restores the independence of O + u, and thus, also P1. It remains to see
why the algorithm preserves also P3. Since the algorithm never removes from O an element
of S, a violation of P3 can only occur when the algorithm considers some element of O \ S.
However, following this consideration one of two things must happen. Either u is also added to
S, or u is placed in Ou and removed from O. In either case P3 is restored.
From this point on, every expression involving S or O is assumed to refer to the final values
of these sets. The following lemma provides a lower bound on f (S) that holds deterministically.
Intuitively, this lemma follows from the observation that, when an element u is considered by
Algorithm 3, its marginal contribution is at least as large as the marginal contribution of any
element of OPT \ S.
P
Lemma 4. f (S) ≥ f (S ∪ OPT) −
|Ou \ S|∆f (u|Su ).
u∈N

Proof. We first show that f (S) ≥ f (O), then we lower bound f (O) to complete the proof. By
P1 and P2, we have O ∈ I and S ⊆ O, and thus, S + v ∈ I for all v ∈ O \ S because (N , I)
is an independence system. Consequently, the termination condition of Algorithm 3 guarantees
that ∆f (v|S) ≤ 0 for all v ∈ O \ S. To use these observations, let us denote the elements of
O \ S by v1 , v2 , . . . , v|O\S| in an arbitrary order. Then
|O\S|

f (O) = f (S) +

X

|O\S|
X

∆f vi |S ∪ {v1 , . . . , v|O\S| } ≤ f (S) +
∆f (vi |S) ≤ f (S) ,

i=1

i=1

where the first inequality follows by the submodularity of f .
It remains to prove the lower bound on f (O). By definition, O is the set obtained from OPT
after the elements of ∪u∈N Ou are removed and the elements of S are added. Additionally, an
element that is removed from O is never added to O again, unless it becomes a part of S. This
implies that the sets {Ou \ S}u∈N are disjoint and that O can also be written as
O = (S ∪ OPT) \ ∪u∈N (Ou \ S) .

(5)

Denoting the the elements of N by u1 , u2 , . . . , un in an arbitrary order, and using the above,

11

we get
f (O) = f (S ∪ OPT) −
≥ f (S ∪ OPT) −
≥ f (S ∪ OPT) −

n
X
i=1
n
X

∆f (Oui \ S|(S ∪ OPT) \ ∪1≤j<i (Oui \ S)) (Equality (5))
∆f (Oui \ S|Sui )

i=1
n
X

X

∆f (v|Sui )

i=1 v∈Oui \S

= f (S ∪ OPT) −

X

X

∆f (v|Sui ) ,

u∈N v∈Ou \S

where the first inequality follows from the submodularity of f because Sui ⊆ S ⊆ (S ∪ OPT) \
∪u∈N (Ou \ S) and the second inequality follows from the submodularity of f as well.
To complete the proof of the lemma we need one more observation. Consider an element
u for which Ou is not empty. Since Ou is not empty, we know that u was considered by the
algorithm at some iteration. Moreover, every element of Ou was also a possible candidate for
consideration at this iteration, and thus, it must be the case that u was selected for consideration
because its marginal contribution with respect to Su is at least as large as the marginal contribution of every element of Ou . Plugging this observation into the last inequality, we get the
following desired lower bound on f (O).
X X
X X
f (O) ≥ f (S ∪ OPT) −
∆f (v|Sui ) ≥ f (S ∪ OPT) −
∆f (u|Sui )
u∈N v∈Ou \S

= f (S ∪ OPT) −

X

u∈N v∈Ou \S

|Ou \ S|∆f (u|Sui ) .

u∈N

While the previous lemma was true deterministically, the next two lemmas are statements
about expected values. At this point, it is convenient to define a new random variable. For every
element u ∈ N , let Xu be an indicator for the event that u is considered by Algorithm 3 in one
of its iterations. The next lemma gives an expression for the expected value of S.
P
1
Lemma 5. E[f (S)] ≥ k+1
E[Xu ∆f (u|Su )].
u∈N

Proof. For each u ∈ N , let Gu be a random variable whose value is equal to in the increase in
the value of S when u is added to S by Algorithm 3. If u is never added to S by Algorithm 3,
then the value of Gu is simply 0. Clearly,
X
X
f (S) = f (∅) +
Gu ≥
Gu .
u∈N

u∈N

By the linearity of expectation, it only remains to show that
E[Gu ] =

1
E[Xu ∆f (u|Su )] .
k+1

(6)

Let Eu be an arbitrary event specifying all random decisions made by Algorithm 3 up until
the iteration in which it considers u if u is considered, or all random decisions made by Algorithm 3 throughout its execution if u is never considered. By the law of total probability,
since these events are disjoint, it is enough to prove that Equality (6) holds when conditioned on
12

every such event Eu . If Eu is an event that implies that Algorithm 3 does not consider u, then,
by conditioning on Eu , we obtain
E[Gu |Eu ] = 0 =

1
1
E[0 · ∆f (u|Su )|Eu ] =
E[Xu ∆f (u|Su )|Eu ] .
k+1
k+1

On the other hand, if Eu implies that Algorithm 3 does consider u, then we observe that Su is a
deterministic set given Eu . Denoting this set by Su0 , we obtain
E[Gu |Eu ] = Pr [u ∈ S | Eu ] ∆f (u|Su0 ) =

1
1
∆f (u|Su0 ) =
E[Xu ∆f (u|Su )|Eu ] .
k+1
k+1

where the second equality hold since an element considered by Algorithm 3 is added to S with
probability (k + 1)−1 .
The next lemma relates terms appearing in the last two lemmata. Intuitively, this lemma
shows that Ou is on average a small set.
Lemma 6. For every element u ∈ N ,
E[|Ou \ S|∆f (u|Su )] ≤

k
E[Xu ∆f (u|Su )] .
k+1

(7)

Proof. As in the proof of Lemma 5, let Eu be an arbitrary event specifying all random decisions
made by Algorithm 3 up until the iteration in which it considers u if u is considered, or all
random decisions made by Algorithm 3 throughout its execution if it never considers u. By
the law of total probability, since these events are disjoint, it is enough to prove Inequality (7)
conditioned on every such event Eu . If Eu implies that u is not considered, then both |Ou |
and Xu are 0 conditioned on Eu , and thus, the inequality holds as an equality. Thus, we may
assume in the rest of the proof that Eu implies that u is considered by Algorithm 3. Notice
that conditioned on Eu the set Su is deterministic and Xu takes the value 1. Denoting the
deterministic value of Su conditioned on Eu by Su0 , Inequality (7) reduces to
E[|Ou \ S| | Eu ]∆f (u|Su0 ) ≤

k
∆f (u|Su0 ) .
k+1

Since u is being considered, it must hold that ∆f (u|Su0 ) > 0, and thus, the above inequality is
k
equivalent to E[|Ou \ S| | Eu ] ≤ k+1
. There are now two cases to consider. If Eu implies that
u ∈ O at the beginning of the iteration in which Algorithm 3 considers u, then Ou is empty if
1
u is added to S and is {u} if u is not added to S. As u is added to S with probability k+1
, this
gives


1
1
k
E[|Ou \ S| | Eu ] ≤
· |∅| + 1 −
|{u}| =
,
k+1
k+1
k+1
and we are done. Consider now the case that Eu implies that u 6∈ O at the beginning of the
iteration in which Algorithm 3 considers u. In this case, Ou is always of size at most k by the
discussion following Algorithm 3, and it is empty when u is not added to S. As u is, again,
1
added to S with probability k+1
, we get in this case


1
1
k
E[|Ou \ S| | Eu ] ≤
·k+ 1−
|∅| =
.
k+1
k+1
k+1
We are now ready to prove Theorem 1.

13

Proof of Theorem 1. We prove here that Algorithm 2 achieves the approximation ratios guaranteed by Theorem 1 for submodular and monotone submodular objectives. The approximation
ratio guaranteed by Theorem 1 for linear objectives is obtained, using similar ideas, by a close
variant of Algorithm 2; and we defer a more detailed discussion of this variant and its guarantee
to Appendix B.
As discussed earlier, Algorithms 2 and 3 have identical output distributions, and so it suffices
to show that Algorithm 3 achieves the desired approximation ratios. Note that
X
E[f (S)] ≥ E[f (S ∪ OPT)] −
E[|Ou \ S|∆f (u|Su )]
(Lemma 4)
u∈N

≥ E[f (S ∪ OPT)] −

k X
E[Xu ∆f (u|Su )]
k+1

(Lemma 6)

u∈N

≥ E[f (S ∪ OPT)] − kE[f (S)] .

(Lemma 5)

If f is monotone, then the proof completes by rearranging the above inequality and observing that f (S ∪ OP T ) ≥ f (OP T ). Otherwise, let us define g : 2N → R≥0 as g(T ) =
f (T ∪ OPT) for every T ⊆ N . One can observe that g is non-negative and submodular. Since
S contains every element with probability at most (k + 1)−1 , we get by Claim 1


k
1
E[f (S ∪ OPT)] = E[g(S)] ≥ 1 −
f (OPT) .
g(∅) =
k+1
k+1
The proof now completes by combining the two above inequalities, and rearranging.

6

Experimental Results

In this section, we present results of an experiment on real dataset comparing the performance
of R EPEATED G REEDY and S AMPLE G REEDY with other competitive algorithms. In particular,
we compare our algorithms to the greedy algorithm and FANTOM, an O(krn)-time algorithm
for nonmonotone submodular optimization introduced in [Mirzasoleiman et al., 2016]. We
also boost S AMPLE G REEDY by taking the best of four runs, denoted Max Sample Greedy.
We test these algorithms on a personalized movie recommendation system, and find that while
R EPEATED G REEDY and S AMPLE G REEDY return comparable solutions to FANTOM, they run
orders of magnitude faster. These initial results indicate that S AMPLE G REEDY may be applied
(without any loss in performance) to massive problem instances that were previously intractable.
In the movie recommendation system application, we observe movie ratings from users,
and our objective is to recommend movies to users based on their reported favorite genres. In
particular, given a user-specified input of favorite genres, we would like to recommend a short
list of movies that are diverse, and yet representative, of those genres. The similarity score
between movies that we use is derived from user ratings, as in [Lindgren et al., 2015].
Let us now describe the problem setting in more detail. Let N be a set of movies, and G be
the set of all movie genres. For a movie i ∈ N , we denote the set of genres of i by G(i) (each
movie may have multiple genres). Similarly, for a genre g ∈ G, denote the set of all movies
in that genre by N (g). Let si,j be a non-negative similarity score between movies i, j ∈ N ,
and suppose a user u seeks a representative set of movies from genres Gu ⊆ G. Note that the
set of movies from these genres is Nu = ∪g∈Gu N (g). Thus, a reasonable utility function for
choosing a diverse yet representative set of movies S for u is
X X
XX
fu (S) =
si,j − λ
si,j
(8)
i∈S j∈Nu

14

i∈S j∈S

for some parameter 0 ≤ λ ≤ 1. Observe that the first term is a sum-coverage function that
captures the representativeness of S, and the second term is a dispersion function penalizing
similarity within S. Moreover, for λ = 1 this utility function reduces to the simple cut function.
The user may specify an upper limit m on the number of movies in his recommended set. In
addition, he is also allowed to specify an upper limit mg on the number of movies from genre
g in the set for each g ∈ Gu (we call the parameter mg a genre limit). The first constraint
corresponds to an m-uniform matroid over Nu , while the second constraint corresponds to the
intersection of |Gu | partition matroids (each imposing the genre limit of one genre). Thus,
our constraints in this movie recommendation corresponds to the intersection of 1 + |Gu | matroids, which is a (1 + |Gu |)-extendible system (in fact, a more careful analysis shows that it
corresponds to a |Gu |-extendible system).
For our experiments, we use the MovieLens 20M dataset, which features 20 million ratings
of 27,000 movies by 138,000 users. To obtain a similarity score between movies, we take an
approach developed in [Lindgren et al., 2015]. First, we fill missing entries of an incomplete
movie-user matrix M ∈ Rn×m via low-rank matrix completion [Candés and Recht, 2008,
Hastie et al., 2015], then we randomly sample to obtain a matrix M̃ ∈ Rn×k where k  m
and the inner products between rows is preserved. The similarity score between movies i and
j is then defined as the inner product of their corresponding rows in M̃ . In our experiment, we
set the total recommended movies limit to m = 10. The genre limits mg are always equal for
all genres, and we vary them from 1 to 9. Finally, we set our favorite genres Gu as Adventure,
Animation and Fantasy. For each algorithm and test instance, we record the function value of
the returned solution S and the number of calls to f , which is a machine-independent measure
of run-time.

(a) Solution Quality

(b) Run Time

(c) Ratio Comparison mg = 1

(d) Ratio Comparison mg = 4

Figure 1: Performance Comparison. 1(a) shows the function value of the returned solutions for
tested algorithms with varying genre limit mg . 1(b) shows the number of function evaluations
on a logarithmic scale with varying genre limit mg . 1(c) and 1(d) show the ratio of solution
quality and cost with FANTOM as a baseline.
Figure 1(a) shows the value of the solution sets for the various algorithms. As we see
15

from Figure 1(a), FANTOM consistently returns a solution set with the highest function value;
however, R EPEATED G REEDY and S AMPLE G REEDY return solution sets with similarly high
function values. We see that Max Sample Greedy, even for four runs, significantly increases
the performance for more constrained problems. Note that for such more constrained problems,
Greedy returns solution sets with much lower function values. Figure 1(b) shows the number
of function calls made by each algorithm as the genre limit mg is varied. For each algorithm,
the number of function calls remains roughly constant as mg is varied—this is due to the lazy
greedy implementation that takes advantage of submodularity to reduce the number of function calls. We see that for our problem instances, R EPEATED G REEDY runs about an order of
magnitude faster than FANTOM and S AMPLE G REEDY runs roughly three orders of magnitude
faster than FANTOM. Moreover, boosting S AMPLE G REEDY by executing it a few times does
not incur a significant increase in cost.
To better analyze the tradeoff between the utility of the solution value and the cost of run
time, we compare the ratio of these measurements for the various algorithms using FANTOM
as a baseline. See Figure 1(c) and 1(d) for these ratio comparisons for genre limits mg = 1 and
mg = 4, respectively. For the case of mg = 1, we see that boosted S AMPLE G REEDY provides
nearly the same utility as FANTOM, while only incurring 1.09% of the computational cost.
Likewise, for the case of mg = 4, R EPEATED G REEDY achieves the same utility as FANTOM,
while incurring only a quarter of the cost. Thus, we may conclude that our algorithms provide
solutions whose quality is on par with current state of the art, and yet they run in a small fraction
of the time.

Figure 2: Solution Sets. The movies in the solution sets for mg = 1 returned by FANTOM,
Sample Greedy, Repeated Greedy and Greedy are listed here, along with genre information.
The favorite genres (Gu ) are in red.
While Greedy may get stuck in poor locally optimal solutions, R EPEATED G REEDY and
S AMPLE G REEDY avoid this by greedily combing through the solution space many times and
selecting random sets, respectively. Fortunately, the movie recommendation system has a very
interpretable solution so we can observe this phenomenon. See Figure 2 for the movies recommended by the different algorithms. Because mg = 1, we are constrained here to have at
most one movie from Adventure, Animation and Fantasy. As seen in Figure 2, FANTOM and
S AMPLE G REEDY return maximum size solution sets that are both diverse and representative of
these genres. On the other hand, Greedy gets stuck choosing a single movie that belongs to all
three genres, thus, precluding any other choice of movie from the solution set.

References
Ashwinkumar Badanidiyuru and Jan Vondrák. Fast algorithms for maximizing submodular
functions. In SODA, 2014.

16

Niv Buchbinder and Moran Feldman. Constrained submodular maximization via a nonsymmetric technique. CoRR, abs/1611.03253, 2016a.
Niv Buchbinder and Moran Feldman. Deterministic algorithms for submodular maximization
problems. In SODA, 2016b.
Niv Buchbinder, Moran Feldman, Joesph (Seffi) Naor, and Roy Schwartz. Submodular maximization with cardinality constrains. In SODA, 2014.
Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. A tight linear time (1/2)approximation for unconstrained submodular maximization. SIAM J. Comput., 44(5):1384–
1402, 2015a.
Niv Buchbinder, Moran Feldman, and Roy Schwartz. Comparing apples and oranges: Query
tradeoff in submodular maximization. In SODA, 2015b.
Gruia Călinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a monotone
submodular function subject to a matroid constraint. SIAM Journal on Computing, 2011.
Emmanuel J. Candés and Benjamin Recht. Exact matrix completion via convex optimization.
In Foundations of Computational Mathematics, 2008.
Vašek Chvátal. The tail of the hypergeometric distribution. Discrete Mathematics, 25(3):285–
287, 1979.
Jack Edmonds. Matroids and the greedy algorithm. Mathematical programming, 1971.
Khalid El-Arini, Gaurav Veda, Dafna Shahaf, and Carlos Guestrin. Turning down the noise in
the blogosphere. In KDD, 2009.
Alina Ene and Huy L. Nguyen. Constrained submodular maximization: Beyond 1/e. In FOCS,
2016.
Uriel Feige, Vahab S. Mirrokni, and Jan Vondrák. Maximizing non-monotone submodular
functions. SIAM Journal on Computing, 2011.
Moran Feldman, Joseph Naor, and Roy Schwartz. A unified continuous greedy algorithm for
submodular maximization. In FOCS, 2011a.
Moran Feldman, Joseph Naor, Roy Schwartz, and Justin Ward. Improved approximations for
k-exchange systems - (extended abstract). In ESA, 2011b.
Marshall L. Fisher, George L. Nemhauser, and Laurence A. Wolsey. An analysis of approximations for maximizing submodular set functions—II. Mathematical Programming, 8:73–87,
1978.
Satoru Fujishige. Submodular functions and optimization. Elsevier Science, 2nd edition, 2005.
Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In
SODA, 2011.
Jennifer Gillenwater, Alex Kulesza, and Ben Taskar. Near-optimal MAP inference for determinantal point processes. In NIPS, 2012.
Manuel Gomez Rodriguez, Jure Leskovec, and Andreas Krause. Inferring networks of diffusion
and influence. In KDD, 2010.
17

Carlos Guestrin, Andreas Krause, and Ajit Paul Singh. Near-optimal sensor placements in
gaussian processes. In ICML, 2005.
Anupam Gupta, Aaron Roth, Grant Schoenebeck, and Kunal Talwar. Constrained nonmonotone submodular maximization: Offline and secretary algorithms. In WINE, 2010.
Trevor Hastie, Rahul Mazumder, Jason D. Lee, and Rexa Zadeh. Matrix completion and lowrank svd via fast alternating least squares. In Journal of Machine Learning Research, 2015.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of
the American Statistical Association, 1963.
Tom A. Jenkyns. The efficacy of the “greedy” algorithm. In South Eastern Conference on
Combinatorics, Graph Theory and Computing, 1976.
David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a
social network. In KDD, 2003.
Katrin Kirchhoff and Jeff Bilmes. Submodularity for data selection in statistical machine translation. In EMNLP, 2014.
Jon Lee, Maxim Sviridenko, and Jan Vondrák. Submodular maximization over multiple matroids via generalized exchange properties. Mathematics of Operations Research, 2010.
Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne Van Briesen, and
Natalie Glance. Cost-effective outbreak detection in networks. In KDD, 2007.
Hui Lin and Jeff Bilmes. A class of submodular functions for document summarization. In
ACL, 2011.
Erik M. Lindgren, Shanshan Wu, and Alexandros G. Dimakis. Sparse and greedy: Sparsifying
submodular facility location problems. In NIPS Workshop on Optimization for Machine
Learning, 2015.
Julián Mestre. Greedy in approximation algorithms. In ESA, pages 528–539, 2006.
Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed submodular maximization: Identifying representative elements in massive data. In NIPS, 2013.
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrak, and Andreas Krause. Lazier than lazy greedy. In AAAI, 2015.
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. Fast constrained
submodular maximization: Personalized data summarization. In ICML, 2016.
George L. Nemhauser and Laurence A. Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 1978.
George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approximations for maximizing submodular set functions—I. Mathematical Programming, 1978.
Colorado Reed and Zoubin Ghahramani. Scaling the indian buffet process via submodular
maximization. In ICML, 2013.
Adish Singla, Ilija Bogunovic, Gábor Bartók, Amin Karbasi, and Andreas Krause. Nearoptimally teaching the crowd to classify. In ICML, 2014.
18

Ruben Sipos, Adith Swaminathan, Pannaga Shivaswamy, and Thorsten Joachims. Temporal
corpus summarization using submodular word coverage. In CIKM, 2012.
Matthew Skala. Hypergeometric tail inequalities: ending the insanity. CoRR, abs/1311.5939,
2013.
Jan Vondrák. Symmetry and approximability of submodular maximization problems. SIAM
Journal on Computing, 2013.
Justin Ward. A (k+3)/2-approximation algorithm for monotone submodular k-set packing and
general k-exchange systems. In STACS, 2012.

A

Hardness of Maximization over k-Extendible Systems

In this appendix, we prove Theorems 3 and 4. The proof consists of two steps. In the first step,
we will define two k-extendible systems which are indistinguishable in polynomial time. The
inapproximability result for linear objectives will follow from the indistinguishability of these
systems and the fact that the size of their maximal sets are very different. In the second step we
will define monotone submodular objective functions for the two k-extendible systems. Using
the symmetry gap technique of [Vondrák, 2013], we will show that these objective functions
are also indistinguishable, despite being different. Then, we will use the differences between
the objective functions to prove the slightly stronger inapproximability result for monotone
submodular objectives.
Given three positive integers k, h and m such that h is an integer multiple of 2k, let us
construct a k-extendible system M(k, h, m) = (Nk.h,m , Ik,h,m ) as follows. The ground set
of the system is Nk,h,m = ∪hi=1 Hi (k, m), where Hi (k, m) = {ui,j | 1 ≤ j ≤ km}. A
set S ⊆ Nk,h,m is independent (i.e., belongs to Ik,h,m ) if and only if it obeys the following
inequality:
gm,k (|S ∩ H1 (k, m)|) + |S \ H1 (k, m)| ≤ m ,
where the function gm,k is defined by




2km
x − 2km/h
,0 .
gm,k (x) = min x,
+ max
h
k
Intuitively, a set is independent if its elements do not take too many “resources”, where most
elements requires a unit of resources, but elements of H1 (k, m) take only 1/k unit of resources
each once there are enough of them. Consequently, the only way to get a large independent set
is to pack many H1 (k, m) elements.
Lemma 7. For every choice of h and m, M(k, h, m) is a k-extendible system.
Proof. First, observe that g(x) is a monotone function, and therefore, a subset of an independent
set of M(k, h, m) is also independent. Also, g(0) = 0, and therefore, ∅ ∈ Ik,h,m . This proves
that M(k, h, m) is an independence system. In the rest of the proof we show that it is also
k-extendible.
Consider an arbitrary independent set C ∈ Ik,h,m , an independent extension D of C and an
element u 6∈ D for which C + u ∈ Ik,h,m . We need to find a subset Y ⊆ D \ C of size at most
k such that D \ Y + u ∈ Ik,h,m . If |D \ C| ≤ k, then we can simply pick Y = D \ C. Thus,
we can assume from now on that |D \ C| > k.

19

Let Σ(S) = g(|S ∩ H1 (k, m)|) + |S \ H1 (k, m)|. By definition, Σ(D) ≤ m because D ∈
Ik,h,m . Observe that g(x) has the property that for every x ≥ 0, k −1 ≤ g(x + 1) − g(x) ≤ 1.
Thus, Σ(S) increases by at most 1 every time that we add an element to S, but decreases by
at least 1/k every time that we remove an element from S. Hence, if we let Y be an arbitrary
subset of D \ C of size k, then
Σ(D \ Y + u) ≤ Σ(D) −

|Y |
+ 1 = Σ(D) ≤ m ,
k

which implies that D \ Y + u ∈ Ik,h,m .
Before presenting the second k-extendible system, let us show that M(k, h, m) contains a
large independent set.
Observation 2. M(k, h, m) contains an independent set whose size is k(m − 2km/h) +
2km/h ≥ mk(1−2k/h). Moreover, there is such set in which all elements belong to H1 (k, m).
Proof. Let s = k(m − 2km/h) + 2km/h, and consider the set S = {u1,j | 1 ≤ j ≤ s}. This
is a subset of H1 (k, m) ⊆ Nk,h,m since s ≤ km. Also,




2km
s − 2km/h
g(|S|) = g(s) = min s,
+ max
,0
h
k


2km
[k(m − 2km/h) + 2km/h] − 2km/h
≤
+ max
,0
h
k


2km
2km
=
+ max m −
,0 = m .
h
h
Since S contains only elements of H1 (k, m), its independence follows from the above inequality.
0
Let us now define our second k-extendible system M0 (k, h, m) = (Nk,h,n , Ik,n
). The
ground set of this system is the same as the ground set of M(k, h, m), but a set S ⊆ Nk,h,m is
considered independent in this independence system if and only if its size is at most m. Clearly,
this is a k-extendible system (in fact, it is a uniform matroid). Moreover, note that the ratio
between the sizes of the maximal sets in M(k, h, m) and M0 (k, h, m) is at least

mk(1 − 2k/h)
= k(1 − 2k/h) .
m
Our plan is to show that it takes exponential time to distinguish between the systems M(k, h, m)
and M0 (k, h, m), and thus, no polynomial time algorithm can provide an approximation ratio
better than this ratio for the problem of maximizing the cardinality function (i.e., the function
f (S) = |S|) subject to a k-extendible system constraint.
Consider a polynomial time deterministic algorithm that gets either Mk,h,m or M0k,h,m
after a random permutation was applied to the ground set. We will prove that with high probability the algorithm fails to distinguish between the two possible inputs. Notice that by Yao’s
lemma, this implies that for every random algorithm there exists a permutation for which the
algorithms fails with high probability to distinguish between the inputs.
Assuming our deterministic algorithm gets M0k,h,m , it checks the independence of a polynomial collection of sets. Observe that the sets in this collection do not depend on the permutation
because the independence of a set in M0k,h,m depends only on its size, and thus, the algorithm
will take the same execution path given every permutation. If the same algorithm now gets
20

Mk,h,m instead, it will start checking the independence of the same sets until it will either get
a different answer for one of the checks (different than what is expected for M0k,h,m ) or it will
finish all the checks. Note that in the later case the algorithm must return the same answer
that it would have returned had it been given M0k,h,m . Thus, it is enough to upper bound the
probability that any given check made by the algorithm will result in a different answer given
the inputs Mk,h,m and M0k,h,m .
Lemma 8. Following the application of the random ground set permutation, the probability
2km
that a set S is independent in Mk,h,m but not in M0k,h,m , or vice versa, is at most e− h2 .
Proof. Observe that as long as we consider a single set, applying the permutation to the ground
set is equivalent to replacing S with a random set of the same size. So, we are interested in
the independence in Mk,h,m and M0k,h,m of a random set of size |S|. If |S| > km, then the
set is never independent in either Mk,h,m or M0k,h,m , and if |S| ≤ m, then the set is always
independent in both Mk,h,m and M0k,h,m . Thus, the interesting case is when m < |S| ≤ km.
Let X = |S ∩ H1 (k, m)|. Notice that X has a hypergeometric distribution, and E[X] =
|S|/h. Thus, using bounds given in [Skala, 2013] (these bounds are based on results of [Chvátal,
1979, Hoeffding, 1963]), we get




2 2
km/h 2
2km
km
2km
− 2k m
= Pr X ≥ E[|X|] +
≤ e−2( |S| ) ·|S| = e h2 ·|S| ≤ e− h2 .
Pr X ≥
h
h
The lemma now follows by observing that X ≤ 2km/h implies that S is a dependent set under
both Mk,h,m and M0k,h,m .
We now think of m as going to infinity and of h and k as constants. Notice that given this
point of view the size of the ground set Nk,h,m is nkh = O(m). Thus, the last lemma implies,
via the union bound, that with high probability an algorithm making a polynomial number (in
the size of the ground set) of independence checks will not be able to distinguishes between the
cases in which it gets as input Mk,h,m or M0k,h,m .
We are now ready to prove Theorem 3.
Proof of Theorem 3. Consider an algorithm that needs to maximize the cardinality function
over the k-extendible system Mk,h,m after the random permutation was applied, and let T
be its output set. Notice that T must be independent in Mk,h,m , and thus, its size is always
upper bounded by mk. Moreover, since the algorithm fails, with high probability, to distinguish
between Mk,h,m and M0k,h,m , T is with high probability also independent in M0k,h,m , and
thus, has a size of at most m. Therefore, the expected size of T cannot be larger than m + o(1).
On the other hand, Lemma 2 shows that Mk,h,m contains an independent set of size at least
mk(1 − 2k/h). Thus, the approximation ratio of the algorithm is no better than
mk(1 − 2k/h)
k
mk(1 − 2k/h)
≥
− o(1) = k − 2k 2 /h − o(1) .
m + o(1)
m
m
Choosing a large enough h (compared to k), we can make this approximation ratio larger than
k − ε for any constant ε > 0.
To prove a stronger inapproximability result for monotone submodular objectives, we need
to associate a monotone submodular function with each one of our k-extendible systems. Towards this goal, consider the monotone submodular function fh : 2Nh → R+ defined over the
ground set Nh = [h] by
fh (S) = min{|S|, 1} .
21

Let Fh : [0, 1]Nh → R≥0 be the mutlilinear extension of fh , i.e., Fh (x) = E[fh (R(x))]
for every vector x ∈ [0, 1]Nh (where R(x) is a random set containing every element u ∈ Nu
with probability xu , independently). Additionally, given a vector x ∈ [0, 1]Nh , let us define
x̄ = (kxk1 /h) · 1Nh . Notice that fh is invariant under any permutation of the elements of Nh .
Thus, by Lemma 3.2 in [Vondrák, 2013], for every ε0 > 0 there exists δh > 0 and two functions
F̂h , Ĝh : [0, 1]Nh → R≥0 with the following properties.
• For all x ∈ [0, 1]Nh : Ĝh (x) = F̂h (x̄).
• For all x ∈ [0, 1]Nh , |F̂h (x) − Fh (x)| ≤ ε0 .
• Whenever |x − x̄|22 ≤ δh , F̂h (x) = Ĝh (x).
• The first partial derivatives of F̂h and Ĝh are absolutely continuous.
•

∂ F̂h ∂ Ĝh
∂xu , ∂xu

•

∂ 2 F̂h
∂ 2 Ĝh
∂xu ∂xv , ∂xu ∂xv

≥ 0 everywhere for every u ∈ Nh .
≤ 0 almost everywhere for every pair u, v ∈ Nh .

The objective function we associate with M(k, h, m) is F̂h (y(S)), where y(S) is a vector
in [0, 1]Nh whose ith coordinate is |S ∩ Hi (k, m)|/(km). Similarly, the objective function we
associate with M0 (k, h, m) is Ĝh (y(S)). Notice that both objective functions are monotone
and submodular by Lemma 3.1 of [Vondrák, 2013]. We now bound the maximum value of a set
in M(k, h, m) and M0 (k, h, m) with respect to their corresponding objective functions.
Lemma 9. The maximum value of a set in M(k, h, m) with respect to the objective F̂h (y(S))
is at least 1 − 2k/h − ε0 .
Proof. Observation 2 guarantees the existence of an independent set S ⊆ H1 (k, m) of size
s ≥ k(m − 2km/h) in M(k, h, m). The objective value associated with this set is
F̂h (y(S)) ≥ Fh (y(S)) − ε0 =

s
k(m − 2km/h)
− ε0 ≥
− ε0 = 1 − 2k/h − ε0 .
km
km

Lemma 10. The maximum value of a set in M0 (k, h, m) with respect to the objective Ĝh (y(S))
is at most 1 − e−1/k + h−1 + ε0 .
Proof. The objective Ĝh (y(S)) is monotone. Thus, the maximum value set in M0 (k, h, m)
must be of size m. Notice that for every set S of this size, we get
Ĝh (y(S)) = F̂h (y(S)) = F̂h ((kh)−1 · 1Nh ) ≤ Fh ((kh)−1 · 1Nh ) + ε0

h


1
1
+ ε0 ≤ 1 − e−1/k + h−1 + ε0 .
=1− 1−
+ ε0 ≤ 1 − e−1/k 1 − 2
kh
k h

As before, our plan is to show that after a random permutation is applied to the ground set it
is difficult to distinguish between M(k, h, m) and M0 (k, h, m) even when each one of them is
accompanied with its associated objective. This will give us an inapproximability result which
is roughly equal to the ratio between the bounds given by the last two lemmata.
Observe that Lemma 8 holds regardless of the objective function. Thus, M(k, h, m) and
M0 (k, h, m) are still polynomially indistinguishable. Additionally, the next lemma shows that
their associated objective functions are also polynomially indistinguishable.
22

Lemma 11. Following the application of the random ground set permutation, the probability
that any given set S gets two different values under the two possible objective functions is at
2
most 2h · e−2mkδh /h .
Proof. Recall that, as long as we consider a single set S, applying the permutation to the ground
set is equivalent to replacing S with a random set of the same size. Hence, we are interested
in the value under the two objective functions of a random set of size |S|. Define Xi = |S ∩
Hi (k, m)|. Since Xi has the a hypergeometric distribution, the bound of [Skala, 2013] gives us
"
"
r #
r #
|S|
δh
δh
+ mk ·
= Pr Xi ≥ E[Xi ] + mk ·
Pr Xi ≥
h
h
h

2
√
mk· δh /h
−2·
·|S|
|S|

= e−

≤e

2δh
h

2 2

· m|S|k

2

≤ e−2mkδh /h .

Similarly, we also get
"

|S|
− mk ·
Pr Xi ≤
h

r

δh
h

#
2

≤ e−2mkδh /h .

Combining both inequalities using the union bound now yields
"
r #
2
|S|
δh
≥ mk ·
≤ 2e−2mkδh /h .
Pr Xi −
h
h
Using the union bound again, the probability that Xi −
is at most 2h · e

−2mkδh /h

2

|S|
h

≥ mk ·

q

δh
h

for any 1 ≤ i ≤ h

. Thus, to prove the lemma it only remainsqto show that the value of

the two objective functions for S are equal when Xi −

|S|
h

< mk ·

δh
h

for every 1 ≤ i ≤ h.

Notice that y(S) is a vector
q|S|/(mkh). Thus, the
qin which all the coordinates are equal to

inequality Xi −

|y(S) −

|S|
h

< mk ·

y(S)|22

=

h
X

δh
h

is equivalent to [yi (S) − yi (S)] <

2

(yi (S) − yi (S)) <

i=1

h
X
i=1

r

δh
h

!2
=

δh
h .

h
X
δh
i=1

h

Hence,

= δh ,

which implies the lemma by the properties of F̂h and Ĝh .
Consider a polynomial time deterministic algorithm that gets either Mk,h,m with its corresponding objective or M0k,h,m with its corresponding objective after a random permutation
was applied to the ground set. Consider first the case that the algorithm gets M0k,h,m (and its
corresponding objective). In this case, the algorithm checks the independence and value of a
polynomial collection of sets (we may assume, without loss of generality, that the algorithm
checks both things for every set that it checks). As before, one can observe that the sets in this
collection do not depend on the permutation because the independence of a set in M0k,h,m and
its value with respect to Ĝh (y(S)) = F̂h (y(S)) depend only on the set’s size, which guarantees
that the algorithm takes the same execution path given every permutation. If the same algorithm
now gets Mk,h,m instead, it will start checking the independence and values of the same sets
until it will either get a different answer for one of the checks (different than what is expected

23

for M0k,h,m ) or it will finish all the checks. Note that in the later case the algorithm must return
the same answer that it would have returned had it been given M0k,h,m .
By the union bound, Lemmata 8 and 11 imply that the probability that any of the sets whose
value or independence is checked by the algorithm will result in a different answer for the
two inputs decreases exponentially in m, and thus, with high probability the algorithm fails to
distinguish between the inputs, and returns the same output for both. Moreover, note that by
Yao’s principal this observation extends also to polynomial time randomized algorithms.
We are now ready to prove Theorem 4.
Proof of Theorem 4. Consider an algorithm that whose objective is to maximize F̂ (y(S)) over
the k-extendible system Mk,h,m after the random permutation was applied, and let T be its
output set. Notice that F̂ (y(T )) ≤ F̂ (1Nh ) ≤ F (1Nh ) + ε0 = 1 + ε0 . Moreover, the algorithm fails, with high probability, to distinguish between Mk,h,m and M0k,h,m . Thus, with
high probability T is independent in M0 (k, h, m) and has the same value under both objective functions F̂ (y(S)) and Ĝ(y(S)), which implies, by Lemma 10, F̂ (y(S)) = Ĝ(y(S)) ≤
1 − e−1/k + h−1 + ε0 . Hence, in conclusion we proved
E[F̂ (y(T ))] ≤ 1 − e−1/k + h−1 + ε0 + o(1) .
On the other hand, Lemma 9 shows that Mk,h,m contains an independent set of value of at
least 1 − 2k/h − ε0 (with respect to F̂ (y(S))). Thus, the approximation ratio of the algorithm
is no better than
1 − 2k/h − ε0
1 − e−1/k + h−1 + ε0 + o(1)
≥ (1 − e−1/k + h−1 + ε0 + o(1))−1 − (1 − e−1/k )−1 (2k/h + ε0 )
≥ (1 − e−1/k )−1 − (1 − e−1/k )−2 (h−1 + ε0 + o(1)) − (1 − e−1/k )−1 (2k/h + ε0 )
≥ (1 − e−1/k )−1 − (k + 1)2 (h−1 + ε0 + o(1)) − (k + 1)(2k/h + ε0 ) ,
where the last inequality holds since 1 − e−1/k ≥ (k + 1)−1 . Choosing a large enough h
(compared to k) and a small enough ε0 (again, compared to k), we can make this approximation
ratio larger than (1 − e−1/k )−1 − ε for any constant ε > 0.

B

Improved Approximation Guarantee for Linear Functions

In Section 5 we described Algorithm 2, which obtains a (k + 1)-approximation for the maximization of a monotone submodular function subject to a k-extendible system constraint. One
can observe that the approximation ratio of this algorithm is no better than k + 1 even when
the function is linear since it takes no element with probability larger than (k + 1)−1 . In this
appendix we show that if the algorithm is allowed to select each element with probability k −1 ,
then its approximation ratio for linear functions improves to k; which proves the guarantee of
Theorem 1 for linear objectives.
Specifically, we consider in this appendix a variant of Algorithm 2 in which the sampling
probability in Line 3 is changed to k −1 . Similarly, the probability in Line 4 of Algorithm 3
is also changed to k −1 in order to keep the two algorithms equivalent. In the rest of this appendix, any reference to Algorithms 2 and 3 should be implicitly understood as a reference to
the variants of these algorithms with the above changes.

24

The analysis we present here for Algorithm 3 (and thus, also for its equivalent Algorithm 2)
is very similar to the one given in Section 5, and it is based on the same ideas. However, slightly
more care is necessary in order to establish the improved approximation ratio of k. We begin
with the following lemma, which corresponds to Lemma 4 from Section 5. For every u ∈ N ,
let Yu be a random variable which takes the value 1 if u ∈ S and, in addition, u does not belong
to O at the beginning of the iteration in which u is considered. In every other case the value of
Yu is 0.
P
Lemma 12. f (S) ≥ f (OPT) −
[|Ou | − Yu ]f (u).
u∈N

Proof. The proof of Lemma 4 begins by showing that f (S) ≥ f (O). This part of the proof is
still true since it is independent of the sampling probability. Thus, we only need to show that
X
f (O) ≥ f (OPT) −
[|Ou | − Yu ]f (u) .
u∈N

Recall that O beings as equal to OPT. Thus, to prove the last inequality it is enough to show
that the second term on its right hand side is an upper bound on the decrease in the value of
O over time. In the rest of the proof we do this by showing that [|Ou | − Yu ]f (u) is an upper
bound on the decrease in the value of O in the iteration in which u is considered, and is equal
to 0 when u is not considered at all.
Let us first consider the case that u is not considered at all. In this case, by definition,
Ou = ∅ and Yu = 0, which imply together [|Ou | − Yu ]f (u) = 0 · f (u) = 0. Consider now
the case that u is considered by Algorithm 3. In this case O is changed during the iteration in
which u is considered in two ways. First, the elements of Ou are removed from O, and second,
u is added to O if it is added to S and it does not already belong to O. Thus, the decrease in the
value of O during this iteration can be written as
X
f (v) − Yu · f (u) .
v∈Ou

To see why this expression is lower bounded by [|Ou | − Yu ]f (u), we recall that in the proof
of Lemma 4 we showed that f (v|Su ) ≤ f (u|Su ) for every v ∈ Ou , which implies, since f is
linear, f (v) ≤ f (u) for every such element v.
The next lemma corresponds to Lemma 5 from Section 5. We omit its proof since it is
completely identical to the proof of Lemma 5 up to change in the sampling probability.
P
P
Lemma 13. E[f (S)] ≥ k1
E[Xu ∆f (u|Su )] = k1
E[Xu ]f (u).
u∈N

u∈N

We need one last lemma which corresponds to Lemma 6 from Section 5. The role of this
lemma is to relate terms appearing in the last two lemmata.
Lemma 14. For every element u ∈ N ,
E[|Ou | − Yu ] ≤

k−1
E[Xu ] .
k

(9)

Proof. As in the proofs of Lemma 6, let Eu be an arbitrary event specifying all random decisions
made by Algorithm 3 up until the iteration in which it considers u if u is considered, or all
random decisions made by Algorithm 3 throughout its execution if it never considers u. By
the law of total probability, since these events are disjoint, it is enough to prove Inequality (9)
25

conditioned on every such event Eu . If Eu implies that u is not considered, then |Ou |, Xu and
Yu are all 0 conditioned on Eu , and thus, the inequality holds as an equality. Thus, we may
assume in the rest of the proof that Eu implies that u is considered by Algorithm 3. Notice that,
conditioned on Eu , Xu takes the value 1. Hence, Inequality (9) reduces to
E[|Ou | − Yu | Eu ] ≤

k−1
.
k

There are now two cases to consider. The first case is that Eu implies that u ∈ O at the beginning
of the iteration in which Algorithm 3 considers u. In this case Yu = 0, and in addition, Ou is
empty if u is added to S, and is {u} if u is not added to S. As u is added to S with probability
1
k , this gives


1
1
k−1
E[|Ou | − Yu | Eu ] ≤ · |∅| + 1 −
|{u}| =
,
k
k
k
and we are done. Consider now the case that Eu implies that u 6∈ O at the beginning of the
iteration in which Algorithm 3 considers u. In this case, if u is not added to S, then we get
Yu = 0 and Ou = ∅. In contrast, if u is added to S, then Yu = 1 by definition and |Ou | ≤ k
by the discussion following Algorithm 3. As u is, again, added to S with probability k1 , we get
in this case


1
1
k−1
E[|Ou | − Yu | | Eu ] ≤ · (k − 1) + 1 −
|∅| =
.
k
k
k
We are now ready to prove the guarantee of Theorem 1 for linear objectives.
Proof of Theorem 1 for linear objectives. We prove here that the approximation ratio guaranteed by Theorem 1 for linear objectives is obtained by (the modified) Algorithm 2. As discussed
earlier, Algorithms 2 and 3 have identical output distributions, and so it suffices to show that
Algorithm 3 achieves this approximation ratio. Note that
X
E[f (S)] ≥ f (OPT) −
E[|Ou | − Yu ]f (u)
(Lemma 12)
u∈N

≥ f (OPT) −

k−1 X
E[Xu ]f (u)
k

(Lemma 14)

u∈N

≥ f (OPT) − (k − 1)E[f (S)] .
The proof now completes by rearranging the above inequality.

26

(Lemma 13)

