1

Distributed Submodular Maximization
with Limited Information

arXiv:1706.04082v1 [] 12 Jun 2017

Bahman Gharesifard

Abstract—We consider a class of distributed submodular
maximization problems in which each agent must choose a
single strategy from its strategy set. The global objective is to
maximize a submodular function of the strategies chosen by
each agent. When choosing a strategy, each agent has access
to only a limited number of other agents’ choices. For each of
its strategies, an agent can evaluate its marginal contribution to
the global objective given its information. The main objective
is to investigate how this limitation of information about the
strategies chosen by other agents affects the performance when
agents make choices according to a local greedy algorithm. In
particular, we provide lower bounds on the performance of
greedy algorithms for submodular maximization, which depend
on the clique number of a graph that captures the information
structure. We also characterize graph-theoretic upper bounds
in terms of the chromatic number of the graph. Finally, we
demonstrate how certain graph properties limit the performance
of the greedy algorithm. Simulations on several common models
for random networks demonstrate our results.

I. I NTRODUCTION
There has been a recent surge of activity in developing
efficient algorithms for large-scale optimization problems, by
partitioning the objective into smaller subtasks, each of which
is optimized separately. A well-studied class of such problems
is the distributed optimization problem, where the main objective is to optimize a sum of functions, each one available to
an individual agent, by means of limited information sharing
between individuals [2], [3], [4], [5], [6], [7], [8], [9], [10].
Unlike this setting, where strategy sets are often assumed to
be continuous sets, here we consider a collaborative scenario,
where agents choose a strategy from a private discrete strategy
set and the goal is to maximize a common objective function
defined over the set of strategies chosen by each agent. In
this sense, this work can be considered as one possible way
to extend the literature on studying distributed optimization
with limited information and continuous strategy sets to combinatorial scenarios. We consider situations where the total
strategy set is partitioned into subsets, each available only
to an individual agent, and the common objective function
is additionally assume to be submodular. When choosing a
strategy, each agent has access to only a limited number
Bahman Gharesifard is with the Department of Mathematics and Statistics
at Queen’s University, Kingston, ON, Canada ghareb@queensu.ca.
Stephen L. Smith is with the Department of Electrical and
Computer Engineering at the University of Waterloo, Waterloo, ON,
Canada stephen.smith@uwaterloo.ca.
The work of the authors was partially supported by the Natural Sciences and
Engineering Research Council of Canada. A preliminary version of this paper
appeared in the Proceedings of the 2016 American Control Conference [1].

Stephen L. Smith

of other agents’ choices, and can evaluate its marginal contribution to the global objective given its information. This
problem arises in a variety of applications of interest, including
problems in distributed sensor coverage [11], [12], information
gathering [13], [14], and facility location [15].
Building on the early classic work [16], [17], [18], [19],
there has been an emerging body of work on sumbodular optimization, mainly due to its wide set of applications to areas of
computer science, see for example [15] and references therein.
It is well known that the submodular maximization problem is
NP-hard [18], unlike submodular minimization, which can be
solved in polynomial time [18]. However, good approximation
algorithms exist; in particular, when the submodular function
is normalized and monotone, a simple greedy algorithm, yields
a solution that is within a multiplicative factor of (1 − 1/e) of
the optimal. The distributed problem we consider in this paper
can be captured as a partition matroid constraint; in particular,
there is a bound on the cardinality of the intersection of the
solution set and the strategy set of each individual agent. It has
been shown [16] that maximizing a normalized and monotone
submodular function subject to a matroid constraint can be
approximated to within 1/2 using the simple greedy algorithm.
More recently [20] a randomized algorithm has been proposed
for this problem, which yields an approximation of (1 − 1/e).
The key feature that differentiates the problem under study
in this paper from the classic setting of submodular maximization is the limitations on the information available to a
decision maker about the strategies chosen by others. Similar
to the literature on distributed optimization, in order to achieve
any reasonable performance, agents need to share information
about their actions. The main objective of this paper is to
investigate how much information is required to guarantee
a certain performance, and what limitations are put on the
performance by the information structure between agents.
It is worth mentioning that parallel computations in submodular optimization has recently generated a lot of interest [21],
[22], [23], [24], [25]. These works focus primarily on largescale maximization or minimization problems, solving them
by partitioning the problem into subsets, each of which is
optimized separately. The overall solution is aggregated and
refined through additional computations by a central node,
often in a MapReduce framework. In our work, however, we
envision scenarios where the limitations imposed on individual
agents is physical (for example, being able to only estimate
data in a neighbourhood). This paper is also somewhat related
to the recent work [11], where the role of limitation of information in submodular optimization is studied in the context

2

of coverage problem, for the cases where agents have full information or no information. Here, we address the limitations
imposed by the information network topology. Finally, part of
our work is related to the so-called “local greedy algorithms”,
which is studied in the classical paper [17], as we describe in
details later.
Statement of Contributions: We consider a class of distributed submodular maximization problems in which each
agent has a strategy set from which it must choose a single
strategy. The global objective is to maximize a submodular
function of the set of strategies chosen by each agent. The
group of agents take decisions sequentially, having available
to them only limited information about the strategies chosen
by previous agents. Each agent can evaluate its marginal
contribution to the global objective given its information. The
information structure is cast as a directed acyclic graph (DAG)
and our main objective is to characterize the fundamental limitations that information limitations impose on the performance
of local greedy algorithms. We first show that the well-known
1
2 lower bound on the performance of greedy algorithms for
submodular maximization can be obtained when the information structure is a complete DAG. We provide a general
lower bound on the performance, which depends on the clique
number of the graph, and also provide lower bounds for
graph topologies with multiple interconnected cliques. We then
characterize graph-theoretic upper bounds on the performance
of the local greedy algorithm. We tackle this objective by
considering two problem statements. In the first one, we
characterize fundamental limitations on the performance of
the greedy algorithms on a given graph topology in terms of
its chromatic number. Our second result demonstrates how
achieving a certain guaranteed performance imposes limitations on the topology of the underlying graph. We characterize
the gap between these two bounds, and show how they can
be used to efficiently compute limitations of distributed greedy
algorithms for scenarios with limited information. Case studies
on several types of randomly generated graphs demonstrate the
relationship between the performance bounds provided and the
true performance of the distributed greedy algorithm.
A preliminary version of this paper appeared as [1]. Relative
to this early work, key contributions include proofs of all results; a treatment of intersecting strategy sets and synchronous
agent updates; applications to sensor coverage; and, extensive
simulation results for several random graph models.
II. P RELIMINARIES
Many combinatorial optimization problems can be phrased
as a submodular maximization problem, which can be stated as
follows. Consider a base set of elements E, and let 2E be the
power set of E, containing all of its subsets. Then a function
f : 2E → R≥0 is submodular if it possesses the property of
diminishing returns: For all A ⊆ B ⊆ S, and for all x ∈ S \B
we have
f (A ∪ {x}) − f (A) ≥ f (B ∪ {x}) − f (B).
We refer to f (A ∪ {x}) − f (A) as the marginal reward of x
given A, and denote it by ∆(x|A). This definition is equivalent

to stating that for all X, Y ⊆ S, we have that
f (X) + f (Y ) ≥ f (X ∪ Y ) + f (X ∩ Y ).

(1)

In addition to submodularity, we will consider functions that
possess two further properties:
(i) Monotonicity: For all A ⊆ B ⊆ E, we have f (B) ≥
f (A); and
(ii) Normalization: f (∅) = 0.
Given a normalized submodular function f defined over a
base set E containing |E| = n elements, along with a positive
integer k < n, the submodular maximization problem can be
stated as
max f (S)
S⊂E

subject to

|S| ≤ k.

(2)
(3)

It is well known that this optimization problem is NP-hard.
It contains as a special case several well known combinatorial
optimization problems including M AX C UT and FACILITY
L OCATION. Even when the function is monotone, the problem
is still NP-hard, and contains as a special case M AX k-C OVER.
When the submodular function is normalized and monotone, a simple greedy algorithm, in which a solution is built
incrementally by adding the element x to S that maximizes
∆(x|S) yields a solution that is within a multiplicative factor
of (1 − 1/e) ≈ 0.63 of the optimal. In addition, it is shown
in [26] that M AX k-C OVER cannot be approximated to a factor
better than (1 − 1/e), unless P = NP. This implies that the
greedy algorithm provides the best possible approximation.
In place of the constraint (3), one can use a more general
form of constraint known as a matroid. The constraint in (3)
defines the uniform matroid in which S must belong to {A ⊆
E : |A| ≤ k}. Another commonly used matroid constraint in
optimization is the partition matroid defined as follows: Let
E be a base set of elements, and partition E into n disjoint
sets E1 , . . . , En and let k1 , . . . , kn be positive integers. Then
allowable sets are members of {A ⊆ E : |A ∩ Ei | ≤ ki }.
It has been shown [16] that maximizing a normalized and
monotone submodular function subject to a matroid constraint
can be approximated to within 1/2 using the simple greedy
algorithm.
III. P ROBLEM S TATEMENT
We begin by introducing a centralized version of the submodular maximization problem studied in this paper.
Consider the following submodular maximization problem.
We are given n disjoint sets Xi , i ∈ {1, . . . , n}, X = ∪i Xi ,
and a submodular monotone and normalized function f :
2X → R≥0 . We wish to solve
max f (S)

S⊆X

subject to
|S ∩ Xi | ≤ 1

for each i ∈ {1, . . . , n}.

(4)

This is a submodular maximization problem over a partition
matroid, and thus from Section II, the optimal solution can

3

be approximated to within a multiplicative factor of 1/2 using
the simple greedy algorithm [16].
A. Distributed Optimization Problem
We consider a collaborative submodular analogue of (4).
Problem 3.1 (Distributed submodular maximization): We
are given n agents, or players V = {1, . . . , n}. Each agent
has an strategy set Xi , and must choose one strategy (or
action) xi ∈ Xi . We define X = ∪i Xi and are given a
normalized and monotone increasing submodular function
f : 2X → R≥0 . The goal is for the agents to each choose an
xi ∈ Xi such that f (x1 , . . . , xn ) is maximized.
We consider the case where agents choose their strategies
in a sequential manner, starting with agent 1 and ending with
agent n. Each agent i ∈ V has access to a subset of the
strategies that have been chosen by agents {1, . . . , i − 1}. This
information is encoded in a directed acyclic graph (DAG) G =
(V, E) where all edges (i, j) ∈ E satisfy i < j. Note that
every DAG can be topologically sorted, and thus there always
exists a labeling of the vertices of G in which i < j for all
(i, j) ∈ E. A complete DAG is a DAG for which no edge can
be added without creating a cycle. A clique in G is a subgraph
of G that is complete. The clique number of a DAG G is the
number of vertices in its largest clique, and is denoted ω(G).
We define the in-neighbors of agent i as
N (i) = {j ∈ V | (j, i) ∈ E},
and thus the information available to agent i when choosing
its strategy is
Xin (i) = {xj | j ∈ N (i)}.
In this paper we study the performance of the greedy
algorithm in which agent i chooses its strategy xi to maximize
its marginal reward relative to its limited information Xin (i):

xi = argmaxx∈Xi ∆ x | Xin (i) .
(5)
In the case where multiple strategies have equal marginal
reward, the greedy algorithm selects one maximizer arbitrarily.
Given a set of strategies {x1 , . . . , xn } for the n agents, the
overall objective can be written as a sum of marginal rewards
as
n
X
f (x1 , . . . , xn ) =
∆(xi | {x1 , . . . , xi−1 }),
(6)
i=1

where {x1 , . . . , x0 } is defined to be the empty set. It is worth
emphasizing that individual agents do not require access to the
function f given in (6). The require only the ability to calculate
their own marginal rewards using the limited information they
have access to in order to compute (5). Note that while xi
that maximizes agent i’s marginal reward relative to Xin ⊆
{x1 , . . . , xi−1 }, its contribution to the overall objective value
is given by the marginal reward relative to {x1 , . . . , xi−1 }.
The main goal of this paper is to investigate how this lack of
information affects the performance of the greedy algorithm.
Remark 3.2 (Topological ordering): In general, there are
multiple topological orderings of a DAG G = (V, E), each

defining a different sequence in which the agents select their
strategies. However, the strategy chosen by each agent will be
identical in all valid orderings, since each agent i must select
its strategy after all agents in Xin (i).
•
Example 3.3 (Sensor coverage): As an illustrative example, consider the setting shown in the left panel of Figure 1.
There are five agents, and each agent i ∈ {1, . . . , 5} has
a strategy set Xi consisting of two elements, which in this
example are disks. Each agent must choose one of its two
disks, and thus as an example, agent 2 must choose one of the
two grey disks labeled with the number 2. The submodular
function f gives the total area covered by the union of the
disks chosen by each agent. The information structure G is
shown in the DAG below the panel. The center panel shows
the disk chosen by each agent under the greedy algorithm (5).
The right panel shows the disks chosen when each agent has
complete information of the choices made before it (i.e., when
G is a complete DAG). We can see that significantly more area
is covered when the agents have complete information.
•
Remark 3.4 (Synchronous agent updates): An alternative
model is that each agent i ∈ V synchronously updates its
strategy based on the strategies of its in-neighbors. That is, let
xi (t) be the strategy of agent i at the synchronous iteration t.
Then, agent i greedily chooses xi (t) to maximize its marginal
reward relative to its in-neighbors choices at t − 1:

xi (t) = argmaxx∈Xi ∆ x | Xin (i, t − 1) ,
where Xin (i, t − 1) = {xj (t − 1) | j ∈ N (i)}. In this case, it
is straightforward to verify that agent k’s strategy is fixed after
iteration k, and its choice of strategy is equal to that in the
sequential setup. Thus, the performance of the synchronous
update is identical to that the sequential update.
•
B. Disjoint vs. Intersecting Strategy Sets
The main results in this paper are bounds on the performance of the greedy algorithm as functions of the information
topology G and the number of agents n. In this section
we show that without loss of generality we can restrict our
attention to disjoint strategy sets. A reader can skip directly
to Section IV and revisit the formal argument later.
Consider Problem 3.1 with information structure G and
strategy sets X1 , . . . , Xn ⊆ X that are possibly intersecting. If the agents run the greedy algorithm in (5), then the
solution S̄ = (x1 , . . . , xn ) produced (written as a tuple to
keep track of the choice of each agent) has two notable
properties: It may contain multiple and/or repeated elements
from a single strategy set. The value of S̄ is evaluated by
defining the set S containing the unique elements of S̄, i.e.,
S = {x ∈ X | S̄(i) = x for some i ∈ {1, . . . , n}}, and
evaluating f (S). As a simple example, if two agents pick the
same strategy x, resulting in the solution S̄ = (x, x), then
S = {x} and the value of the solution is f ({x}).
Now, we define a corresponding problem with the same
number of agents n and information topology G, but with a
submodular function f 0 and disjoint strategy sets X10 , . . . , Xn0
in X 0 = ∪i Xi0 . Define Xi0 as a set containing a unique copy of

4

5
5
3

3

4
2

1

4

3

2

2

5

5

4
2

1

1

4

1

1

3

2

3

4

1

5

2

3

4

5

1

2

3

4

5

Fig. 1. Left: Five agents, each with the choice of two disks. The objective function is the total area covered by the union of disks. Center: The dark numbered
disks show the choice of each agent under limited information. Right: The dark numbered disks show the choice of each agent given complete information
of the choices of prior agents.

0

each element in Xi . We then define a function g : 2X → 2X
that for a set of elements A ⊆ X 0 , returns the corresponding
set of elements in X. Formally, for any set A ⊆ X 0 , we have
g(A) = {x ∈ X | g(a) = x for some a ∈ A}.
g(Xi0 )

Note that
= Xi . By the definition of g, we immediately
see that for any A, B ⊆ X 0 ,
g(A) ∪ g(B) = g(A ∪ B), and g(A) ∩ g(B) = g(A ∩ B).
0

Next, we define the function f 0 : 2X → R≥0 as f 0 = f ◦ g
so that for any A ∈ X 0 ,
f 0 (A) = f (g(A)).
To see that the function is submodular, note that for any
A, B ⊂ X 0 , we have
f 0 (A) + f 0 (B) = f (g(A)) + f (g(B))

where ∆0 is the marginal reward for f 0 . From the definition
that f 0 (A) = f (g(A)), we have that


0
∆0 x0i | Xin
(i) = ∆ xi | Xin (i) .
Suppose now, by way of contradiction, that x0i is not a
maximizer of (7) and there exists a y 0 ∈ Xi0 such that


0
0
∆0 y 0 | Xin
(i) > ∆0 x0i | Xin
(i) .


This would imply that ∆ g(y 0 ) | Xin (i) > ∆ xi | Xin (i) ,
and since g(y 0 ) ∈ Xi , we conclude that xi is not a valid
choice of the greedy algorithm on f , which is a contradiction.
Thus, for every intersecting instance, there is a corresponding
disjoint instance on the same information structure, with
the same optimal solution value, and such that the greedy
algorithm produces solutions with equal value.
IV. T HE SEQUENTIAL DISTRIBUTED GREEDY ALGORITHM :
LOWER BOUND

≤ f (g(A) ∪ g(B)) + f (g(A) ∩ g(B))
= f (g(A ∪ B)) + f (g(A ∩ B))
0

0

= f (A ∪ B) + f (A ∩ B),
where the inequality holds by submodularity of f . If f is
monotone and normalized, then so is f 0 .
Suppose the greedy algorithm (5) constructs a solution
S = {x1 , . . . , xn } on the non-disjoint instance f . Consider
any S 0 = {x01 , . . . , x0n } such that x0i ∈ Xi0 and g(xi ) = x0i .
What remains is to show that S 0 is a solution of the greedy
algorithm (5) when run on the disjoint instance f 0 . Also, since
g(S 0 ) = S the solutions have equal value, f 0 (S 0 ) = f (S).
0
By recalling the definition of Xin (i) and defining Xin
(i) =
0
{xj | j ∈ N (i)}, we have
0
Xin (i) = g(Xin
(i)).

xi = argmaxx∈Xi ∆(x|∅).
Suppose that {x∗1 , x∗2 , . . . , x∗n } be the solution of (4), where
x∗i ∈ Xi for each i ∈ {1, . . . , n}. We have that
f (x1 , . . . , xn ) ≥ f (xi ) ≥ f (x∗i ),
for all i ∈ {1, . . . , n}, and hence
n

f (x1 , . . . , xn ) ≥

Now, we need to verify that x0i satisfies

0
x0i = argmaxx0 ∈Xi0 ∆0 x0 | Xin
(i) ,

Throughout this section, we assume that the strategy sets
are disjoint. The agents take their decisions sequentially in
increasing order according to their index. We start with a
scenario where the agents do not observe the strategies of the
agents that have taken action prior to them (see Figure 2(a)).
The decision of agent i ∈ V is then

(7)

1
1X
f (x∗i ) ≥ f (x∗1 , . . . , x∗n ),
n i=1
n

where the last inequality follows from submodularity of f
given by (1). It is easy to observe that this lower bound is

5

tight and cannot be improved. A natural problem is hence
to investigate if this lower bound on the performance can be
improved when the agents can observe (perhaps partially) the
decisions of the preceding agents before making decisions.
Consider the scenario where agent i observes the decision of
all agents in the set Ii = {1, . . . , i − 1}. The information
that each agent has access to before taking its decision is best
represented by Figure 2(b). In this case, the decision for agent
i from (5) becomes
xi = argmaxx∈Xi ∆(x|{x1 , . . . , xi−1 }).

(8)

k and we show it holds for k + 1. We have
f (x1 , . . . ,xk+1 )
=f (x1 , . . . , xk ) + ∆(xk+1 |x1 , . . . , xk )
≥f (x1 , . . . , xk−1 , x∗1 , . . . , x∗k ) − f (x1 , . . . , xk−1 )
+ ∆(x∗k+1 |x1 , . . . , xk )
=f (x1 , . . . , xk−1 , x∗1 , . . . , x∗k ) − f (x1 , . . . , xk−1 )
+ f (x1 , . . . , xk , x∗k+1 ) − f (x1 , . . . , xk ),

(10)

where in the first inequality we applied the inductive hypothesis and the greedy choice property. Next, using submodularity,
we have
f (x1 , . . . ,xk−1 , x∗1 , . . . , x∗k ) + f (x1 , . . . , xk , x∗k+1 )

(11)

≥ f (x1 , . . . , xk , x∗1 , . . . , x∗k+1 ) + f (x1 , . . . , xk−1 ).
1
1

2

3

2

3

n

Substituting (11) into the right hand side of (10) and cancelling
the common f (x1 , . . . , xk−1 ) term we get

n

(a)

(b)

Fig. 2. (a) shows a scenario with no observation and (b) shows a scenario
where each agents observes the decisions of all the preceding agents.

The performance of the strategy proposed by (8) can be
deduced from the so-called “local greedy algorithms”, which
is studied in the classical paper [17, Theorem 4.1]. The proof
presented in [17] relies on a clever use of linear programming.
Here we present an independent proof that allows us to extend
this result to more general information topologies. We start
with the following result.
Lemma 4.1: Consider Problem 3.1 and let (x∗1 , x∗2 , . . . , x∗n )
be an optimal solution. Suppose that players sequentially
update their strategies (x1 , . . . , xn ) according to (8). Then,
for all 1 ≤ k ≤ n, we have that
f (x1 , . . . , xk ) ≥

f (x∗1 , . . . , x∗k )

− f (x1 , . . . , xk−1 ).

(9)

Proof: We prove the following slightly stronger result,
f (x1 , . . . , xk+1 ) ≥ f (x1 , . . . , xk , x∗1 , . . . , x∗k+1 )
− f (x1 , . . . , xk ).
Note that the result in (9) immediately follows after proving
this, since
f (x1 , . . . , xk , x∗1 , . . . , x∗k+1 ) ≥ f (x∗1 , . . . , x∗k+1 ),
by monotonicity. The proof will proceed by induction.
Throughout the proof, we use the “greedy choice property”,
i.e., the fact that
∆(xk+1 |x1 , . . . , xk ) ≥ ∆(x∗k+1 |x1 , . . . , xk ).
First, consider the base case of k = 0. By the greedy choice
property, we have that
f (x1 ) ≥ f (x∗1 ),
and the the base case holds. Next, suppose the result holds for

f (x1 , . . . , xk+1 ) ≥ f (x1 , . . . , xk , x∗1 , . . . , x∗k+1 )
− f (x1 , . . . , xk ),
which proves the result.
Theorem 4.2: Consider
Problem
3.1
and
let
(x∗1 , x∗2 , . . . , x∗n ) be an optimal solution. Suppose that
players sequentially update their strategies (x1 , . . . , xn )
according to (8). Then
f (x1 , . . . , xn ) ≥

1
f (x∗1 , . . . , x∗n ).
2

Proof: Using Lemma 4.1, we have
f (x1 , . . . , xn ) ≥ f (x∗1 , . . . , x∗n ) − f (x1 , . . . , xn−1 ).
Also, by monotonicity, we have f (x1 , . . . , xn )
≥
f (x1 , . . . , xn−1 ), and hence the result follows.
The following consequence of this result holds for any
general directed acyclic graph.
Corollary 4.3: Consider
Problem
3.1
and
let
(x∗1 , x∗2 , . . . , x∗n ) be an optimal solution. Suppose that
players sequentially update their strategies (x1 , . . . , xn )
according to (5) on a directed acyclic graph G. Then,
f (x1 , . . . , xn ) ≥

1
f (x∗1 , . . . , x∗n ),
(n − ω(G)) + 2

where ω(G) is the clique number of G.
Proof: Let us partition the nodes in G into to the set of
nodes in a maximum clique, whose strategy sets are denoted by
Sclique with its complement S̄clique . Consider now the smaller
optimization problem over Sclique . By Theorem 4.2,
1
∗
f (Sclique
),
2
where we have again used the star notation to denote the
optimal solution. On the other hand, the remaining n − ω(G)
1
agents cannot have a performance worst than n−ω(G)
of their
optimal, i.e.,
f (Sclique ) ≥

f (S̄clique ) ≥

1
∗
f (S̄clique
).
n − ω(G)

6

Using these two inequalities, we conclude that
∗
∗
f (Sclique
) + f (S̄clique
) ≤ 2f (Sclique ) + (n − ω(G))f (S̄clique )

≤ (2 + (n − ω(G))f (S),
where S = Sclique ∪ S̄clique , and the last inequality follows by
monotonicity of f . Using the submodularity of f , we have
∗
∗
that f (S ∗ ) ≤ f (Sclique
) + f (S̄clique
) and hence
f (S ∗ ) ≤ (2 + (n − ω(G))f (S),

where (x̃∗mκ−1 , . . . , x̃∗mκ ) is the optimal strategy for clique κ.
Hence, we also have that
f (xmκ−1 , . . . , xmκ ) ≥

1
f (x∗mκ−1 , . . . , x∗mκ ),
2

where (x∗mκ−1 , . . . , x∗mκ ) is the strategy for clique κ in the
true optimal. By using monotonicity, we have that
2f (x1 , . . . , xn ) ≥ f (x∗mκ−1 , . . . , x∗mκ ).

concluding the proof.
On the other hand, by the induction assumption, along with
monotonicity, we have that
2(κ−1)f (x1 , . . . , xmκ−1 ) ≥

f (x∗1 , . . . , x∗mκ−1 ) +

κ−2
X

f (x∗mi ).

i=1

Fig. 3. A DAG with 8 nodes is depicted, where ω(G) = 5. By Corollary 4.3,
we conclude that under (5), we have f (x1 , . . . , xn ) > 61 f (x∗1 , . . . , x∗n ).

Figure 3 shows an example where Corollary 4.3 is used
to conclude the performance of (5). Note that if we take a
complete DAG and delete a single edge, it’s clique number
reduces from n to n − 1, and from Corollary 4.3, our lower
bound decreases from 1/2 to 1/3. The reason for this is that we
have not made any assumptions on the relative contribution of
each player to the total reward. The one agent that is removed
from the clique may contribute more to the total reward than
all n − 1 other agents combined.

Summing the last two inequalities, and noting that by monotonicity f (x1 , . . . , xn ) ≥ f (x1 , . . . , xmκ−1 ) since n = mκ ,
we have that
2κf (x1 , . . . , xn ) ≥f (x∗1 , . . . , x∗mκ−1 )
+f (x∗mκ−1 , . . . , x∗mκ )

+

κ−2
X
i=1

Using submodularity, we have that
2κf (x1 , . . . , xn ) ≥f (x∗1 , . . . , x∗mκ )
+ f (x∗mκ−1 ) +

A. Interconnected Cliques of Full Information

f (x∗mi ).

κ−2
X

f (x∗mi )

i=1

It is not clear how to characterize the impact of the
availability or lack of information on the performance of local
greedy algorithms for arbitrary graph topologies. In this subsection, however, we extend Theorem 4.2 to a scenario with
multiple cliques, where the agent’s in each clique have access
to the decision of the last agent in the last clique that takes
decision prior to them.
Theorem 4.4: Consider
Problem
3.1
and
let
(x∗1 , x∗2 , . . . , x∗n ) be an optimal solution. Suppose that
agents are partitioned into κ ∈ Z≥1 cliques as
{1, . . . , m1 }, {m1 + 1, . . . , m2 }, · · · {mκ−1 + 1, . . . , n},
with the only information available from other cliques to the
agent’s in (i + 1)’s clique being the choice of agent mi , i ∈
{1, . . . , κ − 1}. Suppose that players sequentially update their
strategies (x1 , . . . , xn ) according to (5). Then
f (x1 , . . . , xn ) ≥

1
(f (x∗1 , . . . , x∗n ) +
2κ

κ−1
X

f (x∗mi )).

i=1

Proof: We proceed by induction on κ. The base case,
where κ = 1, follows from Theorem 4.2. Suppose now that
the statement holds for κ − 1. We prove that it also holds for
κ. For notational convenience, let us define mκ := n. First,
by Theorem 4.2,
f (xmκ−1 , . . . , xmκ ) ≥

1
f (x̃∗mκ−1 , . . . , x̃∗mκ ),
2

= f (x∗1 , . . . , x∗n ) +

κ−1
X

f (x∗mi ),

i=1

concluding the proof.
As noted in Remark 3.4, the results of this section are extend
to the case of synchronous updates. As a final observation,
consider the setting of Theorem 4.4 and suppose that there is
no communications between agents in the cliques. Then, since
1
f (x∗1 , . . . , x∗m1 ), and
2
1
f (xmi +1 , . . . , xmi+1 ) ≥ f (x∗mi +1 , . . . , x∗mi+1 ),
2
f (x1 , . . . , xm1 ) ≥

for all i ∈ {1, . . . , κ−1}, using submodularity and monotonic1
f (x∗1 , . . . , x∗n ). In
ity, we conclude that f (x1 , . . . , xn ) ≥ 2κ
this sense, Theorem 4.4 captures a scenario where the overall
performance can only be enhanced by having access to more
information. In particular, the performance is guaranteed to
improve by at least
κ−1
1 X
1
f (x∗mi ) ≥
f (x∗m1 , . . . , x∗mκ−1 ) ≥ 0,
2κ i=1
2κ

where the first inequality holds by submodularity.

7

V. U PPER BOUNDS USING COLOURING
Our main objective in this section is to determine upper
bounds on the performance of the sequential greedy algorithm.
We proceed with studying two cases: 1) we construct a graph
dependent submodular function that exploits information on
graph topology to yield an upper bound; and 2) we design a
global submodular function that provides bounds on all graph
topologies. We will see that these two cases are essentially
equivalent to computing an optimal and a greedy coloring [27]
of the graph, respectively. The second case also allows us to
extract graph properties that limit performance.
A. Background on Graph Coloring
Given a graph G = (V, E) with |V | = n, a coloring is a
function c : V → {1, . . . , n} such that for every (u, v) ∈ V ,
we have c(u) 6= c(v). The vertex-coloring problem is to find
a coloring c : V → {1, . . . , k} such that k is minimized.
That is, the goal is to color the vertices of the graph with
the minimum number of colors such that no pair of adjacent
vertices have the same color. The optimum value of k is called
the chromatic number of the graph G and is often denoted by
χ(G). The problems of computing a minimum coloring or
equivalently of determining the chromatic number of a graph
are NP-hard [27].
B. Upper Bound via Adversarial Choice of Function
Consider the following problem: Given a graph G = (V, E),
can we construct a submodular function fG , exploiting information of the graph for which we can upper bound the
performance of greedy algorithm? We call such a function
adversarial since the function can be designed to exploit
the weaknesses of the information graph. Given a graph
G = (V, E), we construct strategy sets and a submodular
function as follows. Let c : V → {1, . . . , k} be an optimal
coloring of G and where χ(G) = k is the chromatic number
of G. Given a coloring, we define the set of vertices of color
` ≤ k as
V` = {v ∈ V | c(v) = `}.
We use this coloring to construct strategy sets Xi for each
agent i ∈ V and the submodular function f : 2X → R≥0 .
For each agent i, we define Xi = {ai , bi }, and let X = ∪i Xi .
We define the function f through its marginal rewards. To that
end, let S ⊂ X be a set such that |S ∩ Xi | ≤ 1 containing
decision for a subset of the n agents in V . Then, the marginal
reward of ai is defined as
(
0 if aj ∈ S for some j ∈ Vc(i) ,
∆(ai |S) =
1 otherwise.
The marginal reward of bi is defined is ∆(bi |S) = 1, for
all i ∈ V . Then, given a set S = {s1 , . . . , sm } ⊂ X with
|S ∩ Xi | ≤ 1, for all i ∈ V , we define
f (S) =

m
X
i=1


∆ si |{s1 , . . . , si−1 } .

(12)

1

2

3

4

5

1

2

3

Fig. 4. A minimum coloring of the graph of Figure 3 using five colors. Using
the lower bounds on the performance and Proposition 5.1, we can conclude
that 16 f (x∗1 , . . . , x∗n ) < f (x1 , . . . , xn ) < 58 f (x∗1 , . . . , x∗n ).

Note that we can equivalently define this function over nondisjoint strategy sets. Let X = {a, b1 , . . . , bn } and define
Xi = {a, bi }. Then given a set S ⊂ X, we define f (S) = |S|.
Notice that this function is modular. Given a tuple containing
agent strategies (x1 , . . . , xn ), we define the set of unique
strategies as S = {x1 , . . . , xn } and evaluate f (S) as the
reward. This definition is equivalent to the disjoint definition
above as discussed in Section III-B.
Using the function (12), we obtain the following result.
Proposition 5.1: Consider Problem 3.1, where f is given
by (12), and let (x∗1 , x∗2 , . . . , x∗n ) be an optimal solution.
Suppose that players sequentially update their strategies
(x1 , . . . , xn ) according to (5). Then,
f (x1 , . . . , xn ) ≤

χ(G)
f (x∗1 , . . . , x∗n ).
n

Proof: An optimal solution for maximizing (12) is x∗i =
bi for each i ∈ V , which yields a reward of f (x∗1 , . . . , x∗n ) =
n. Now, considering the greedy algorithm in (5), we see that
for each agent i ∈ V , we have N (i) ∩ Vc(i) = ∅, and thus no
agent in Vc(i) is visible to agent i. Thus, for each agent i we
have

argmaxx∈Xi ∆ x | Xin (i) = {ai , bi },
both of which achieve a marginal reward of 1. A possible
evolution of the greedy algorithm is xi = ai for each i ∈ V .
The value of this solution is
f (a1 , . . . , an ) =

n
X

∆(ai | a1 , . . . , ai−1 ) = χ(G)

i=1

since only the first agent of each color contributes 1 to the
total reward, and all others contribute zero.
Figure 4 depicts the DAG used in Figure 3 along with
an optimal coloring yielding a chromatic number of 5. Using Proposition 5.1, we conclude that under (5), we have
f (x1 , . . . , xn ) < 85 f (x∗1 , . . . , x∗n ).
C. Upper Bound via Universal Function
The upper bound in the previous section required a submodular function f that depended on the graph. In the following,
we propose a single function, independent of the graph topology, and analyze its performance for all graphs. This allows
us to state a few simple properties of graphs that limit its
performance.
The base set of the function is X = {e1 , . . . , em } where
m ≥ n and we let Xi = X for each agent i. Given a choice

8

xi ∈ Xi for each agent i, the value of the submodular function
is
f (x1 , . . . , xn ) = | ∪i {xi }|.

(13)

That is, the value is given by the number of unique elements
of X chosen by the agents. Clearly, an optimal solution is any
one in which each agent chooses a different element from X,
yielding a value of n. Under the greedy algorithm, agent i will
compute its marginal reward as
(
1 if ej ∈
/ Xin (i)
∆(ej | Xin (i)) =
0 if ej ∈ Xin (i),
and thus agent i will choose any strategy ej such that ej ∈
/
Xin (i). Suppose that each agent i breaks ties by choosing the
strategy with lowest index. Then, we can write the greedy
choice for agent i as
xi = min{ej ∈ X | ej ∈
/ Xin (i)}.

(14)

Next we relate the performance of the greedy algorithm on
this function to properties of the underlying graph.
Proposition 5.2: Consider the submodular function in (13)
and any graph G = (V, E). If the greedy algorithm finds a
solution within k/n of the optimal for some k > 0 then each
of the following properties hold:
(i) there is a vertex in G with in-degree of at least k − 1;
(ii) for each ` ∈ {1, . . . , k} there are at least ` agents with
in-degree of at least k − `;
(iii) the number of edges in G is at least k(k − 1)/2.
Proof: By Equation (14), if xi = ej , then
{e1 , . . . , ej−1 } ⊆ Xin (i). From this we immediately see that
for an agent to choose ek , it must have an in-degree of at
least k − 1, proving property (i). Property (ii) also follows by
noticing that each agent that chooses a strategy with index ≥ j
must have in-degree of at least j − 1. To achieve a value of
k, each strategy from e1 to ek must be chosen by an agent.
To see property (iii), we notice
Pk that the sum of in-degrees
of all agents must be at least j=1 j = k(k − 1)/2.
Notice that the sequence of strategy choices in (14) provides
a simple and efficient algorithm for computing a performance
upper bound for a given graph. For completeness, we give the
details in Algorithm 1.
Algorithm 1 Greedy Algorithm Upper Bound
Input: A directed acyclic graph G = (V, E).
Output: An upper bound on the approximation ratio of
greedy algorithm on G.
1: Topologically sort the vertices V
2: for each v ∈ V :
3:
Set value[v] = 1
4: for each v ∈ V in topological order :
5:
Set value[v] to smallest integer k such that for each
u ∈ N (i), value[u] 6= k.
6: return |V1 | maxv∈V value[v]

u4

w4

u3

w3

u2

w2

u1

w1

Fig. 5. A bipartite graph on eight vertices. The graph is colored using just
two colors, and its chromatic number is two. Under (14), vertex w4 will select
strategy e5 , and thus Algorithm 1 will output 5/8.

Complexity of Algorithm 1: The complexity of Algorithm 1
is O(|V | + |E|). The topological sort can be performed in
O(|V | + |E|) time. The only detail is to implement line 5: in
linear time, which essentially computes the smallest element
not in an array. This can be done using two passes through
the array of in-neighbor values. In the first pass, we populate
a Boolean array of length |N (i)|. All entries of the array are
initialized to false, and the jth entry is then reset to true
if and only if there is a vertex u ∈ N (i) with value[u] = j.
In the second pass, we scan the Boolean array for the first
false entry. This is the smallest value that is not chosen by an
in-neighbor. Thus, the total computation time for the for-loop
in line 4: is O(|E|).
D. Gap Between Adversarial and Universal Upper Bounds
The strategies chosen by each agent for the submodular
function in (13) provides a coloring of the graph G. That is,
the vertices V` := {i ∈ V | xi = e` } are those colored with
color `. By construction, there are no edges between vertices of
the same color. This implies that the adversarial upper bound
is tighter than the universal upper bound, which utilizes the
minimum number of colors.
A key question is how large the gap can be between the two
upper bounds. In general it can be arbitrarily large. To see this,
consider the following bipartite directed graph G = (V, E)
consisting of n = 2m vertices, where
V = {u1 , . . . , um } ∪ {w1 , . . . , wm }.
The graph contains all edges (ui , wj ) such that i < j and all
edges (wi , uj ) such that i < j along with the edge (um , wm ).
An example is shown in Figure 5. We fix the topological
ordering of the vertices to be u1 , w1 , u2 , w2 , . . . , um , wm . For
this graph, under Algorithm 1, the vertex wm chooses strategy
em+1 . Thus
(i) the chromatic number of G is 2, and thus the adversarial
upper bound is 2/n; and
(ii) Algorithm 1 returns 1/2 + 1/(2m).
However, the advantage of Algorithm 1 is that it is a
simple linear-time algorithm for computing an upper bound on
achievable performance of a given graph topology. In contrast,
the adversarial function of Section V-B provides a much tighter
upper bound, but requires solving an NP-hard problem. An
interesting connection to note is that Algorithm 1 is essentially

9

computing a greedy coloring of G, where vertices are considered in topological order. It is known that in general a greedy
coloring does not provide a constant factor approximation to
the minimum coloring [27].
Remark 5.3 (Gap between bounds for random graphs):
Given a probability p ∈ [0, 1] and a set V of n vertices, the
Erdös-Rényi graph G(n, p) on V is a random graph in which
each edge (i, j), where i, j ∈ V and i 6= j is included with
probability p. From [28], the chromatic number of almost
every G(n, p) is



n
1
+ o(1) log(1/(1 − p))
.
2
log n

VI. S IMULATION R ESULTS
In this section we explore the relation between the lower
bound, the two upper bounds, and the true performance of
the greedy algorithm on several types of randomly generated
graphs. The classes of random graphs chosen here are ErdösRényi, Barabási-Albert preferential attachment, and WattsStrogatz model graphs, which are commonly used to model
social networks [29], as well as physical networks [30]. Given
a graph G, we compute the chromatic number χ(G) and the
and clique number ω(G) using their standard integer programming formulations [31], and solve each integer program using
Gurobi [32].

������������������������

����

In addition, for almost every graph G(n, p), the greedy coloring uses at most twice as many colors [28]. Consider now
random directed acyclic graphs generated as follows: we first
generate an Erdös-Rényi graph, and then we use any correct
method to assign directions to each edge such that the resulting
directed graph becomes acyclic. Then, using the result above
on the chromatic number of the underlying Erdös-Rényi graph,
Algorithm 1 provides


1
1
+ o(1) log(1/(1 − p))
2
log n

����

����

����

����
���

as an upper bound on the performance. In addition, for almost
every graph G(n, p), the greedy coloring uses at most twice
as many colors [28], implying that for such graphs the gap
between the two upper bounds is at most two.
•

E. Comparison of Lower and Upper Bounds
In Section IV, we provided lower bounds on the performance of greedy algorithm (8) for any monotone, normalized,
submodular function. This consisted of results for several
graph topologies, and a general result based on the clique
number of the graph. Table I compares these lower bounds
with the upper bounds obtained from Proposition 5.1 and
Algorithm 1. Given a graph topology, the lower bound provides a minimum performance guarantee for all submodular
functions. In constrast, the upper bounds provide limitations on
performance for a specific (worst-case) submodular function.
Graph

Lower

χ(G) Upper

Alg. 1 Upper

Empty
Complete acyclic
Interconnected cliques
General DAG

1/n
1/2
1/(2κ)

1/n
1
1/κ + 1/n
χ(G)/n

1/n
1
1/κ + 1/n
Alg. 1

1
n−ω(G)+2

TABLE I
C OMPARISON BETWEEN THE LOWER BOUND IN S ECTION IV AND THE
TWO UPPER BOUNDS FOR THREE GRAPH TOPOLOGIES .

The entires in Table I for the interconnected cliques graph
assume κ cliques, each of size n/κ.

���

���

���

���

���������������

Fig. 6. Comparison between the upper bound from Algorithm 1 and the
performance on the distributed greedy algorithm over 100 random graphs.
The value of the upper bound correlates strongly with the true performance
of the distributed greedy algorithm (Spearman’s rank correlation coefficient
of 0.92).

First, we explored the relation between the true performance
of the distributed greedy algorithm and the upper bound given
by Algorithm 1. We generated a submodular function using
the disk coverage problem illustrated in Figure 1 with 50
agents. Each agent has the choice of three disks each of
radius r = 0.07, uniformly randomly distributed in the unit
square. We then generated 100 random graphs describing
the information structure between the agents. Each graph is
generated as follows. We select a probability p uniformly
randomly from [0, 1], generate a directed Erdos-Renyi graph
with probability p, fix a random ordering of the vertices,
and delete all edges that are directed to an earlier vertex in
the ordering, creating a random DAG. Figure 6 displays the
results on these 100 graphs. The upper bound, which is an
approximation ratio relative to the global optimal, and the
value obtained by the distributed greedy algorithm, which is
the fraction of the unit square covered by the selected disks,
are highly correlated.
Next, Figure 7 compares the lower bound to the two
upper bounds for graphs generated according to the BarabásiAlbert preferential attachment model [33] a function of the
number of vertices in the graph (i.e., the number of agents
in the network). Each graph is created by starting with a
complete graph on five vertices, and then adding vertices using
preferential attachment. An acyclic graph is then created by

10

generating a random ordering of the vertices and deleting
cyclic edges as described above. Each data point shows the
mean of 20 preferential attachment graphs, where error bars
give the standard deviation. The figure gives insight into the
8

ratio between upper and lower bound

alg 1 upper
chromatic upper

7
6
5
4
3

Each data point shows the mean of 20 small-world graphs,
where error bars give the standard deviation. As the number
of neighbors K increases, the graphs become more connected.
When K = 12, each vertex is connected to all others, and
thus the resulting DAG is complete. Of note in this figure
is the relatively small gap between the two upper bounds,
which gives support to the use of Algorithm 1 as an efficient
approximation to the chromatic number bound. Also of note is
the large change in the ratio of the bounds as K is increased
from 11 to 12. Recall that for a complete DAG (i.e., K = 12),
the lower bound is 1/2, while the upper bounds are both 1. On
the other hand, as discussed immediately after Corollary 4.3,
removing even just a single edge from a complete DAG has
a large impact on the lower bound, which is observed in the
large change in the ratio.

2
1

5

10

15

20

25

30

35

VII. C ONCLUSIONS AND FUTURE WORK

40

number of agents

Fig. 7. Ratio between upper and lower bounds as a function of the number of
agents for networks formed via preferential attachment. Each graph is grown
from a complete directed graph on 5 nodes, and each new node is connected
to five neighbors using the preferential attachment rule. Each data point shows
the mean of 20 trials, and error bars give the standard deviation.

gap between lower and upper bounds, and the growth of this
gap with the number of agents. Note, this plot shows the
dependence of the bounds on the information structure, and
holds for all functions f .
Finally, Figure 8 compares the lower bound to the two upper
bounds for small-world graphs created according to the WattsStrogatz model [34]. In this experiment, each graph begins as
a ring lattice over 25 vertices, where each vertex is connected
to K neighbors on each side. The value of K is plotted on the
horizontal axis in Figure 8. Then, each edge is rewired with a
probability β = 0.25, by shifting one of its endpoints to a new
vertex at random, while avoiding self-loops and duplication of
edges. A DAG is then created by fixing a random ordering of
the vertices, and removing acyclic edges, as described above.

We have studied a class of submodular maximization
problems under matroid constraint, where the strategy set is
partitioned into private strategy sets, assigned to a group of
agents; in this sense, the maximization task is distributed
among them. The agents take actions sequentially and have
limited information about the actions taken by agents prior
to them. We have investigated the limitations that the lack of
information about the actions of other agents can impose by
characterizing upper and lower bounds on the performance of
local greedy algorithms. Our lower bound depend on the clique
number of a graph that captures the information structure,
whereas our upper bounds are given in terms of the chromatic
number of the underlying graph. Studying scenarios where
agents are allowed to modify their choices in multiple rounds,
obtaining tighter upper bounds for more homogeneous classes
of submodular functions, investigating under what additional
assumptions on the submodular functions one can generalize
the lower bounds provided, and exploring other applications
of distributed submodular optimization are interesting avenues
of future research.
ACKNOWLEDGMENTS

ratio between upper and lower bound

9

The authors wish to thank Mohd. Shabbir Ali and Professor
Jason Marden for their useful comments on an earlier version
of this paper. We also thank the associate editor and the
reviewers for their helpful comments.

alg 1 upper
chromatic upper

8
7
6

R EFERENCES

5
4
3
2
1

2

4

6

8

10

12

number of neighbors

Fig. 8. Ratio between upper and lower bounds as a function of the number of
neighbors for each agent prior to the rewiring operation. Each graph contains
25 agents, and the rewiring probability β = 0.25. Each data point shows the
mean of 20 trials, and error bars give the standard deviation.

[1] B. Gharesifard and S. L. Smith, “On distributed submodular maximization with limited information,” in American Control Conference,
pp. 1048–1053, July 2016.
[2] J. N. Tsitsiklis, D. P. Bertsekas, and M. Athans, “Distributed asynchronous deterministic and stochastic gradient optimization algorithms,”
IEEE Transactions on Automatic Control, vol. 31, no. 9, pp. 803–812,
1986.
[3] M. Rabbat and R. Nowak, “Distributed optimization in sensor networks,”
in Symposium on Information Processing of Sensor Networks, (Berkeley,
CA), pp. 20–27, Apr. 2004.
[4] L. Xiao and S. Boyd, “Optimal scaling of a gradient method for
distributed resource allocation,” Journal of Optimization Theory &
Applications, vol. 129, no. 3, pp. 469–488, 2006.

11

[5] A. Nedic and A. Ozdaglar, “Distributed subgradient methods for multiagent optimization,” IEEE Transactions on Automatic Control, vol. 54,
no. 1, pp. 48–61, 2009.
[6] P. Wan and M. D. Lemmon, “Event-triggered distributed optimization
in sensor networks,” in Symposium on Information Processing of Sensor
Networks, (San Francisco, CA), pp. 49–60, 2009.
[7] A. Nedic, A. Ozdaglar, and P. A. Parrilo, “Constrained consensus and
optimization in multi-agent networks,” IEEE Transactions on Automatic
Control, vol. 55, no. 4, pp. 922–938, 2010.
[8] B. Johansson, M. Rabi, and M. Johansson, “A randomized incremental
subgradient method for distributed optimization in networked systems,”
SIAM Journal on Control and Optimization, vol. 20, no. 3, pp. 1157–
1170, 2009.
[9] B. Gharesifard and J. Cortés, “Distributed continuous-time convex optimization on weight-balanced digraphs,” IEEE Transactions on Automatic
Control, vol. 59, no. 3, pp. 781–786, 2014.
[10] A. Nedic and A. Olshevsky, “Distributed optimization over time-varying
directed graphs,” IEEE Transactions on Automatic Control, vol. 60,
no. 3, pp. 601–615, 2015.
[11] J. R. Marden, “The role of information in distributed resource allocation,” IEEE Transactions on Control of Network Systems, 2016. To
appear.
[12] S. T. Jawaid and S. L. Smith, “Submodularity and greedy algorithms in
sensor scheduling for linear dynamical systems,” Automatica, vol. 61,
pp. 282–288, 2015.
[13] A. A. Ageev and M. I. Sviridenko, “Pipage rounding: A new method of
constructing algorithms with proven performance guarantee,” Journal of
Combinatorial Optimization, vol. 8, no. 3, pp. 307–328, 2004.
[14] S. T. Jawaid and S. L. Smith, “Informative path planning as a maximum
traveling salesman problem with submodular rewards,” Discrete Applied
Mathematics, vol. 186, pp. 112–127, 2015.
[15] A. Krause and D. Golovin, “Submodular function maximization,”
Tractability: Practical Approaches to Hard Problems, vol. 3, p. 19, 2012.
[16] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An analysis of approximations for maximizing submodular set functions-I,” Mathematical
Programming, vol. 14, no. 1, pp. 265–294, 1978.
[17] M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, “An analysis of
approximations for maximizing submodular set functions-II,” in Mathematical Programming Study 8, pp. 73–87, North-Holland Publishing
Company, 1978.
[18] L. Lovász, “Submodular functions and convexity,” in Mathematical
Programming The State of the Art, pp. 235–257, Springer, 1983.
[19] S. Fujishige, Submodular functions and optimization, vol. 58. Elsevier,
2005.
[20] G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák, “Maximizing a
monotone submodular function subject to a matroid constraint,” SIAM
Journal on Computing, vol. 40, no. 6, pp. 1740–1766, 2011.
[21] B. Mirzasoleiman, A. Karbasi, R. Sarkar, and A. Krause, “Distributed
submodular maximization: Identifying representative elements in massive data,” in Advances in Neural Information Processing Systems,
pp. 2049–2057, 2013.
[22] B. Mirzasoleiman, A. Karbasi, R. Sarkar, and A. Krause, “Distributed
submodular maximization,” arXiv preprint arXiv:1411.0541, 2014.
[23] P. Stobbe, Convex analysis for minimizing and learning submodular set
functions. PhD thesis, California Institute of Technology, 2013. Ph.D.
thesis.
[24] A. Clark, B. Alomair, L. Bushnell, and R. Poovendran, “Scalable
and distributed submodular maximization with matroid constraints,” in
Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks
(WiOpt), 2015 13th International Symposium on, pp. 435–442, 2015.
[25] R. d. P. Barbosa, A. Ene, H. L. Nguyen, and J. Ward, “A new framework
for distributed submodular maximization,” in Foundations of Computer
Science (FOCS), 2016 IEEE 57th Annual Symposium on, pp. 645–654,
IEEE, 2016.
[26] U. Feige, “A threshold of ln(n) for approximating set cover,” Journal
of the ACM, vol. 45, no. 4, pp. 634–652, 1998.
[27] B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, vol. 21 of Algorithmics and Combinatorics. Springer, 4 ed.,
2007.
[28] B. Bollobás and P. Erdös, “Cliques in random graphs,” Mathematical
Proceedings of the Cambridge Philosophical Society, vol. 80, no. 03,
pp. 419–427, 1976.
[29] N. Bof, G. Baggio, and S. Zampieri, “On the role of network centrality in
the controllability of complex networks,” IEEE Transactions on Control
of Network Systems, 2016. to appear.

[30] S. Soltan, D. Mazauric, and G. Zussman, “Analysis of failures in power
grids,” IEEE Transactions on Control of Network Systems, 2016. to
appear.
[31] J. Pattillo and S. Butenko, “Clique, independent set, and graph coloring,” Encyclopedia of Operations Research and Management Science,
pp. 3150–3163, 2011.
[32] Gurobi Optimization, Inc., “Gurobi optimizer reference manual,” 2016.
[33] A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” science, vol. 286, no. 5439, pp. 509–512, 1999.
[34] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’
networks,” nature, vol. 393, no. 6684, pp. 440–442, 1998.

