Multi-Agent and Multivariate Submodular
Optimization
Richard Santiago1 and F. Bruce Shepherd2

arXiv:1612.05222v2 [cs.DS] 19 Dec 2016

1

McGill University, Canada, richard.santiagotorres@mail.mcgill.ca
2
McGill University, Canada, bruce.shepherd@mcgill.ca

Abstract. Recent years have seen many algorithmic advances in the area of submodular optimization: (SO) min / max f (S) : S ∈ F, where F is a given family of feasible
sets over a ground set V and f : 2V → R is submodular. This progress has been coupled with a wealth of new applications for these models. Our focus is on a more
general class of multi-agent submodular optimization
(MASO) which was introduced
P
by Goel et al. in the minimization setting: min i fi (Si ) : S1 +S2 +· · ·+Sk ∈ F. Here
we use + to denote disjoint union and hence this model is attractive where resources
are being allocated across k agents, each with its own submodular cost function fi ().
In this paper we explore the extent to which the approximability of the multi-agent
problems are linked to their single-agent primitives.
We present a generic reduction that transforms a multi-agent (and more generally
multivariate) problem into a single-agent one, showing that several properties of the
objective function and family of feasible sets are preserved. For maximization, this allows one to leverage algorithmic results from the single-agent submodular setting for
the multi-agent case. We are not aware of work for general families in the maximization setting and so these results substantially expand the family of tractable models.
For instance, we see that multi-agent (and multivariate) maximization subject to a
p-matroid constraint can be reduced to a single-agent problem over the same type
of constraint (i.e., p matroid intersections). Allowing the (much) more general class
of multivariate submodular
P objective functions f (S1 , S2 , . . . , Sk ) (instead of decomposable functions f = i fi ) gives new modelling capabilities. We describe a family
of multivariate submodular objectives based on quadratic functions and show how
these may be used to penalize competition between agents.
For monotone multi-agent minimization we give three types of reductions. The first
two are black-box reductions which show that (MASO) has an O(α·min{k, log2 (n)})approximation when (SO) over F admits an O(α)-approximation over the natural
formulation. The third type of reduction is for the special case when every element
in the blocking clutter of F has size at most β. Here we show that β-approximations
and β ln(n)-approximations are always available for the single-agent and multi-agent
problems respectively. Moreover, virtually all known approximations for single-agent
monotone submodular minimization are derived in this way.

1

Introduction

For a family of feasible sets S ∈ F on a finite ground set V we consider the following broad
class of submodular optimization (SO) problems:
SO(F )

Min / Max f (S) : S ∈ F

(1)

where f is a submodular set function on V . We call these two problems the “primitives”
associated with F . There has been an impressive recent stream of activity around these

2

Richard Santiago and F. Bruce Shepherd

problems for various set families F . We explore the connections between these primitive
problems and their multi-agent incarnations. In the multi-agent (MA) version, we have k
agents each of which has an associated submodular set function fi , i ∈ [k]. As before, we
are looking for sets S ∈ F , however, we now have a 2-phase task: the elements of S must
also be partitioned amongst the agents. Hence we have set variables Si and seek to optimize
P
k
i fi (Si ). This leads to the multi-agent submodular optimization (MASO) versions:
P
(2)
MASO(F )
Min / Max
i fi (Si ) : S1 + S2 + · · · + Sk ∈ F .
The special case when F = {V } was previously examined but the general form was only
introduced and developed in Goel et al. [12] for the minimization setting. A natural first
question is whether any multi-agent problem could be reduced (or encoded) to a single-agent
one. Goel et al. show this is not the case. The following simple submodular-cost problem
has a MA cost function which cannot be realized by a single submodular cost function over
the same ground set V . There are three tasks {A, B, C} and two agents {1, 2}. Each agent
can do one of the tasks at cost 1 each. In addition agent 1 can do tasks {A, B} at cost
of only 1, and {A, B, C} at cost of only 2. Agent 2 can do {A, C} at cost of only 1, and
{A, B, C} at cost of only 2. We can associate a cost c(S) for any subset S ⊆ {A, B, C} which
corresponds to the best allocation of tasks in S to the agents. This function c(S) is not,
however, submodular even though each agent’s cost function was submodular. To see this,
note that the marginal cost of adding B to {A} is 0 which is smaller than the marginal cost
of adding it to {A, C}.
Perhaps even more emphatically, they prove that when F consists of vertex covers in a
graph, the single-agent (SA) version (i.e., (1)) has a 2-approximation while the MA version
has an inapproximability lower bound of Ω(log(n)). One of our main objectives is to explain
the extent to which approximability for multi-agent problems is intrinsically connected to
their single-agent versions.
In some cases our methods get traction for a more general class of problems that we call
the capacitated multi-agent submodular optimization (CMASO) problem
CMASO(F )

Pk
max / min
i=1 fi (Si )
s.t. S1 + · · · + Sk ∈ F
Si ∈ Fi , ∀i ∈ [k]

(3)

where we are supplied with the subfamilies Fi . Many existing applications fit into this
framework and some of these can be enriched through the added flexibility of the capacitated
model. For instance, one may include set bounds on the variables: Li ⊆ Si ⊆ Ui for each
i, or simple cardinality constraints: |Si | ≤ bi for each i. Applications which fit into this
framework are discussed further in Section 1.2.
1.1

Multivariate Submodular Optimization

Multi-agent optimization can be seen as a special case of a much more general class of multivariate submodular optimization (MVSO) problems. Namely functions of several variables
which satisfy some type of submodularity properties. In this paper, we call a multivariate
function f : (2V )k → R multi-submodular (or sometimes multivariate submodular) if for all
pairs of tuples (S1 , ..., Sk ), (T1 , ..., Tk ) ∈ (2V )k we have
f (S1 , ..., Sk ) + f (T1 , ..., Tk ) ≥ f (S1 ∪ T1 , S2 ∪ T2 , .., Sk ∪ Tk ) + f (S1 ∩ T1 , ..., Sk ∩ Tk ).

Multi-Agent and Multivariate Submodular Optimization

3

We mention that other extensions have been considered in the literature, including [46,43,20,23].
Notice that in the special case of k = 1 a multi-submodular function corresponds to a univariate submodular function. Hence, the above can be thought as a natural extension of
submodularity to multivariate functions. Since the objective functions used in CMASO are
multi-submodular, this leads to a more general class of problems:
CMVSO(F )

max / min f (S1 , S2 , . . . , Sk )
s.t. S1 + · · · + Sk ∈ F
Si ∈ Fi , ∀i ∈ [k].

(4)

While several of our multi-agent results extend to the multivariate setting, the class
of multi-submodular functions can encode much more than the “decomposable” functions
arising in multi-agent objectives. We give complexity-theoretic evidence of this in Section 5
where we establish (see Corollary 11 and Lemma 6) a large gap between the following two
problems.
P
min
min g(S1 , . . . , Sk )
i∈[k] gi (Si )
s.t. S1 + · · · + Sk = V
s.t. S1 + · · · + Sk = V
(MA − Min)
(MV − Min)
Si ⊆ Vi
Si ⊆ Vi
|Si | ≤ 1
|Si | ≤ 1
Proposition 1. The problem (MV-Min) is Ω(n)-inapproximable under the oracle model
(even if g is monotone and nonnegative) whereas the problem (MA-Min) has an exact polytime algorithm (for arbitrary submodular functions gi ).
The remainder of the introduction is structured as follows. In Section 1.3, we describe
our generic reductions which turn MA (and in some cases, the more general multivariate)
optimization problems into a SA primitive. This reduction together with recent algorithmic
advances in (SA) submodular optimization imply that many interesting instances of CMASO
become tractable. Prior work in both the single and multi-agent settings is summarized in
Section 1.4. We believe that the CMASO and CMVSO frameworks have potential for future
applications and so we start by presenting some existing examples which fit into, and can
be further extended, in these models.
1.2

Some Applications of Capacitated Multi-Agent and Multivariate
Optimization

In this section we present several problems in the literature which are special cases of
Problem (3). We also indicate cases where the extra generality of CMASO gives modelling
advantages. We postpone the algorithmic and complexity results until Section 1.4. We start
by discussing the maximization setting.
Example 1 (The Submodular Welfare Problem). The most basic problem in the maximization setting arises when we simply take the feasible space F = {V }. This describes a
well-known model (introduced in [31]) for allocating goods from a ground set to agents,
each of which has a submodular valuation (utility) function over baskets of goods. This is
formulated as (3) by considering nonnegative monotone functions fi , F = {V }, and Fi = 2V
for all i. The computational problem is then
Pk
max
i=1 fi (Si )
s.t. S1 + · · · + Sk = V.

4

Richard Santiago and F. Bruce Shepherd

Example 2 (Sensor Placement with Multivariate Objectives). The problem of placing sensors and information gathering has been popular in the submodularity literature [24,27,25].
We are given a set of sensors V and a set of possible locations {1, 2, . . . , k} where the sensors
can be placed. There is also a budget constraint restricting the total number of sensors that
can be deployed. The goal is to place sensors at some of the locations so as to maximize the
“informativeness” gathered. We argue below that this application is well suited to a multivariate submodular objective function f (S1 , ..., Sk ) which measures the “informativeness”
of placing sensors Si at location i. A natural mathematical formulation for this is given by
max
f (S1 , ..., Sk )
s.t. S1 + · · · + Sk ∈ F
Si ∈ F i ,
where F := {S ⊆ V : |S| ≤ b} imposes the budget constraint and Fi gives additional
modelling flexibility for the types (or number) of sensors that can be placed at location i.
For instance, we could impose a cardinality constraint |Si | ≤ bi by defining Fi = {S ⊆
V : |S| ≤ bi }. We could also impose that only sensors Vi ⊆ V can be placed at location
i by taking Fi = {S ⊆ V : S ⊆ Vi }. We can also combine these constraints by taking
Fi = {S ⊆ Vi : |S| ≤ bi }. Notice that in these cases both F and the Fi are matroids
and hence our algorithms
will apply. One may form a multivariate objective by defining
P
f
(S
f (S1 , S2 , . . . , Sn ) =
i i i ) − R(S1 , S2 , . . . , Sn ) where the fi ’s measure the benefit of
placing sensors Si at location i, and R() is a redundancy function. If the fi ’s are submodular
and R() is multivariate supermodular, then f is multivariate submodular. In this setting,
it is natural to take the fi ’s to be coverage functions (i.e. fi (Si ) measures the coverage of
placing sensors Si at location i). We next propose a family of “redundancy” functions which
are supermodular.
Supermodular penalty measures via Quadratic functions. We denote S :=
(S1 , S2 , . . . , Sn ) and define zS := (|S1 |, |S2 |, . . . , |Sn |). One can show (see Lemma 14 in
Appendix C) that if A is a matrix satisfying aij +aji ≥ 0, then R(S) := zST AzS is multivariate
supermodular. For instance, in the example, one could take redundancy coefficients aij as
1
Θ( d(i,j)
2 ) where d(i, j) denotes the distance between locations i and j. This can be further
extended so that
P different sensor types contribute different weights to the vector zS , e.g.,
define zS (i) = j∈Si w(j) for an associated sensor weight vector w. We believe that these
quadratic functions (based on matrices satisfying aij + aji ≥ 0) yield a useful class of
multivariate submodular functions for modelling “competition” between agents in many
domains other than sensor problems.
Example 3 (Recommendation Systems and Matroid Constraints). This has been a widely
deployed class of problems that usually entails the targetting of product ads to a mass
of (largely unknown) buyers or “channels”. In [5] a “meta” problem is considered where
(known) prospective buyers are recommended to interested sellers. This type of recommendation system incurs additional constraints such as (i) bounds on the size of the buyer list
provided to each seller (possibly constrained by a seller’s advertising budget) and (ii) bounds
on how often a buyer appears on a list (so as to not bombard them). They model these constraints as a “b-matching” problem in a bipartite buyer-seller graph GB . They also consider
a more exotic model which incorporates “conflict-aware” constraints on the buyer list for
each seller (e.g., no more than two buyers from the same household). Conflicts are modelled
by extra edges amongst the buyer nodes: the subgraph of buyers recommended to a seller has
an upper bound on the number of allowed conflict edges. Heuristics for this (linear-objective)

Multi-Agent and Multivariate Submodular Optimization

5

model [5] are successfully developed on Ebay data, even though the computational problem
was shown to be NP-hard. In fact, subsequent work [4] shows that conflict-aware b-matching
is unlikely to have a polytime algorithm which approximates the optimum to within factors
of O(n1−ǫ ). We now propose an alternative model which admits an O(1)-approximation.
For sellers with diminishing returns, a natural alternative to a linear objective
function
P
is a decomposable multivariate submodular objective f (S1 , S2 , . . . , Sk ) = i fi (Si ) where
Si denotes the list of buyers recommended to seller i. (Multivariate supermodular penalty
functions, discussed in the previous example, may also be used to tap into competition
between sellers.) The model (3) can now be used to reformulate the conflict constraints so
as to avoid the aforementioned polynomial inapproximability. We consider the problem
Pk
max
i=1 fi (Si )
s.t. S1 ∪ S2 . . . ∪ Sk ∈ F
Si ∈ Fi , ∀i ∈ [k]
where F is a partition matroid on the buyers enforcing the upper bound on the number
of times a buyer is recommended. We define Fi to enforce constraints for the seller. First,
we may restrict the family to the feasible buyers Vi ⊆ V for each seller i. Second we may
partition Vi into “households” Vij and require that seller i’s list include at most 1 element
from each Vij . Thus Fi is a partition or laminar matroid. Our results will show that this
version has a polytime O(1)-approximation (in the oracle model).
Example 4 (Public Supply Chain). Consider the problem of transporting resources from the
hinterland to external markets served by a single port. As prices fluctuate the underlying
value of resources changes and this motivates the expansion of public or private networks.
These problems have a large number of stakeholders such as port authority, multiple train
and trucking carriers, labor unions and overseeing government transportation bodies. It
is not uncommon for one good (say coal) to be transported by several distinct organizations and even more than one firm involved in the same mode of transport (say rail). The
design and expansion of such networks therefore represent examples of strong multi-agent
behaviour. Moreover, feasible sets based on matroid constraints lend themselves to very natural transportation structures such as arborescences (which are a special case of intersection
of two matroids).
We now discuss Problem (3) in the minimization setting.
Example 5 (Minimum Submodular Cost Allocation). Similar to the maximization setting,
the most basic problem in the minimization setting arises when we simply take the feasible
space F = {V }, and the agents are allowed to take any subset of V (i.e. Fi = 2V for all i).
This problem,
Pk
min
i=1 fi (Si )
s.t. S1 + · · · + Sk = V,
has been widely considered in the literature for both monotone and nonmonotone functions
[42,7,3], and is referred to as the Minimum Submodular Cost Allocation (MSCA)
problem3 (introduced in [17,42] and further developed in [3]).
The framework from (3) allows us to incorporate additional constraints into the MSCA
problem by defining the families Fi appropriately. The most natural are to impose cardinality
3

Sometimes referred to as submodular procurement auctions.

6

Richard Santiago and F. Bruce Shepherd

constraints on the number of elements that an agent can take, or to only allow agent i
to take a set Si of elements satisfying some bounds Li ⊆ Si ⊆ Ui . For instance, in the
Submodular Facility Location problem, one can model that a potential facility must serve
some customers, and may only serve customers within a pre-specified region given by Ui .
These are discussed in detail on Section 5.
Example 6 (Multi-agent Minimization). Goel et al [12] consider the case of Problem (3) for
monotone, submodular functions in which F is a nontrivial collection of subsets of V (i.e.
F ⊂ 2V ) and there is no restriction on the Fi (i.e. Fi = 2V for all i). In particular, given a
graph G they consider the families of vertex covers, spanning trees, perfect matchings, and
shortest st paths.
Example 7 (Rings). It is known [40] that arbitrary submodular functions can be minimized
efficiently on a ring family, i.e. a family of sets closed under unions and intersections (see [38]
for faster implementations, and work on modified ring families [14]). A natural extension
is to minimization of multivariate submodular functions over a multivariate ring family,
where by the latter we mean a family of tuples closed under (component wise) unions and
intersections. We provide the formal definitions in Section 2.4 and show that this more
general problem can still be solved efficiently by applying the reduction from Section 2.
1.3

Our Contributions

We discuss a generic reduction that transforms the multivariate problem (4) (and hence (3))
into a single-agent problem. The reduction uses the simple idea of viewing assignments of
elements v to agents i in a multi-agent bipartite graph (this was first proposed by Nisan et
al in [32] and also used in Vondrak’s work [44]; in these cases F = {V }). The associated
bipartite graph is G([k], V ) = ([k] + V, E) where there is an edge iv for each i ∈ [k] and each
v ∈ V . Any valid assignment of some elements in V to agents corresponds to a b-matching
Z in G, where b[i] = ∞ for each i ∈ [k] and b(v) = 1 for each v ∈ V .
While the above auxiliary graph is fine when F = {V } (as in [32,44]), in general multiagent optimization problems we may use a subset F ⊂ V from a general family F . Hence
we are seeking b-matchings Z for which cov(Z) ∈ F . Here we define cov(Z) to be the set of
nodes v ∈ V which are saturated by Z. There is no apriori reason that these F -constrained
b-matchings should have any nice structure, even for simple F . Our first result (Section 2)
is that indeed this is the case if F is a matroid.
Theorem 1. If F induces a matroid over V , then so does the family of F -constrained
b-matchings over the edges of the multi-agent bipartite graph G.
Moreover, nice structure is also maintained if we start with a family of matroid bases
or an intersection of p matroids. This, together with the recent advances in SA submodular
optimization (Section 1.4), yields the following algorithmic consequences.
Theorem 2. Consider the capacitated multivariate maximization problem
max f (S1 , S2 , . . . , Sk )
s.t. S1 + · · · + Sk ∈ F
Si ∈ Fi , ∀i ∈ [k]
where f is a nonnegative multivariate submodular function and the families Fi are matroids.
Then we have the following results.

Multi-Agent and Multivariate Submodular Optimization

7

1. If F is a matroid, then there is a (2 + ǫ)-approximation for monotone functions and
a (2 + O(1))-approximation for nonmonotone functions. Moreover, in the special case
where Fi = 2V for all i, there is a (1 − 1e )-approximation for monotone functions and a
1
e -approximation for nonmonotone functions.
2. If F is a p-matroid intersection, then there is a (p + 1 + ǫ) and a (p + 1 + O(1))approximation for monotone and nonmonotone functions respectively. Moreover, in the
case where Fi = 2V for all i, there is a (p + ǫ) for monotone functions.
3. If F is the set of bases of a matroid and Fi = 2V for all i, then there is a (1 − 1e )approximation for monotone functions and a 21 (1 − ν1 )-approximation for nonmonotone
functions where ν denotes the fractional base packing number.
The nice properties of the reduction also allow us to leverage results for single-agent
robust submodular maximization to the multivariate setting. The robustness considered in
this case is with respect to the adversarial removal of up to τ elements. We point out that
while this paper does not focus on robust formulations, we believe that this result may be of
independent interest and could lead to interesting applications and future work. We prove
the following.
Theorem 3. Consider the multivariate robust maximization problem
max
min
f (S1 − A1 , S2 − A2 , . . . , Sk − Ak ),
S1 + · · · + Sk ∈ F PAi ⊆ Si
Si ∈ F i
i |Ai | ≤ τ
where f is a nonnegative monotone multivariate submodular function and the families Fi
are matroids. Then we have the following.
1. There is a [(τ + 1)(p + 1 + ǫ)]-approximation for any fixed ǫ > 0 in the case where F is
a p-matroid intersection.
τ +1
)-approximation in the case
2. In the special case where Fi = 2V for all i, there is a ( 1−1/e
where F is a matroid, and a [(τ + 1)(p + ǫ)]-approximation for any fixed ǫ > 0 in the
case where F is a p-matroid intersection.
On the minimization side, there exist polynomial inapproximability results even in the
single-agent setting subject to a matroid constraint (e.g. cardinality constraint [41] or spanning trees [12]). Hence the “good behaviour” of the reduction (Theorem 1) is not directly
applicable. However, we describe two different connections (in terms of n and in terms of k)
between MA and SA optimization. These are based on the natural “blocking” LP relaxation;
see Appendices A and B.
Theorem 4. Suppose there is a (polytime) α(n)-approximation for the single-agent nonnegative monotone submodular minimization problem based on rounding the natural LP
for a family F . Then there is a (polytime) O(α(n) · min{k, log2 (n)})-approximation for the
multi-agent nonnegative monotone submodular minimization problem over F . Moreover, the
O(kα(n))-approximation extends to the more general multivariate setting.
In Section 4, we revisit the state for constrained minimization primitives and spotlight
some new cases of interest which have good approximability properties. Given a family F
the blocker B(F ) of F consists of the minimal sets B such that B ∩ F 6= ∅ for each F ∈ F .
We say that B(F ) is β-bounded if |B| ≤ β for all B ∈ B(F ). Our results can be summarized
as follows.

8

Richard Santiago and F. Bruce Shepherd

Theorem 5. Let F be a family with a β-bounded blocker. Then there are β-approximation
and β ln(n)-approximation algorithms for the associated single-agent and multi-agent nonnegative monotone problems respectively. These yield polytime algorithms if P ∗ (F ) has a
polytime separation oracle.
Corollary 1. If B(F ) is β-bounded and there is a polytime separation oracle for the blocking
formulation of F , then there is a polytime β-approximation for the above minimization
problem.
We mention that this result implies the 2-approximation for vertex cover, and k-approximation
for k-uniform hitting set, which are the only “good” approximations (known to us) for the
minimization version of (1) for nontrivial families F [12,19].
1.4

Related Work

Single Agent Optimization. The high level view of the tractability status for unconstrained (i.e., F = 2V ) submodular optimization is that both maximization and minimization are generally behave well. Minimizing a submodular set function is a classical combinatorial optimization problem which can be solved in polytime [15,40,18]. Unconstrained
maximization on the other hand is known to be inapproximable for general submodular
set functions but admits a polytime constant-factor approximation algorithm when f is
nonnegative [1,9].
In the constrained maximization setting, the classical work [36,37,11] already established an optimal (1 − 1e )-approximation factor for maximizing a nonnegative monotone
submodular function subject to a cardinality constraint, and a (k + 1)-approximation for
maximizing a nonnegative monotone submodular function subject to k matroid constraints.
This approximation is almost tight in the sense that there is an (almost matching) factor
Ω(k/ log(k)) inapproximability result. For nonnegative monotone functions [44,2] give an
optimal (1 − 1e )-approximation based on multilinear extensions when F is a matroid; [28]
provides a (1 − 1e − ǫ)-approximation when F is given by a constant number of knapsack
constraints, and [30] gives a local-search algorithm that achieves a (k + ǫ)-approximation
(for any fixed ǫ > 0) when F is a k-matroid intersection. For nonnegative nonmonotone
functions, a 1e -approximation is known [10] for maximization under a matroid constraint, in
[29] a (k + O(1))-approximation is given for k matroid constraints with k fixed. A simple
“multi-greedy” algorithm [16] matches the approximation of Lee et al. but is polytime for
any k. Finally, Vondrak [45] gives a 12 (1 − ν1 )-approximation under a matroid base constraint
where ν denotes the fractional base packing number.
Recently, Orlin et al [39] considered a robust formulation for constrained monotone
submodular maximization, previously introduced by Krause et al [26]. The robustness in
this model is with respect to the adversarial removal of up to τ elements. The problem
can be stated as maxS∈F minA⊆S,|A|≤τ f (S − A), where F is an independence system.
Assuming an α-approximation is available for the special case τ = 0 (i.e. the non-robust
α
)-approximation for the robust problem.
version), [39] gives an ( τ +1
For constrained minimization, the news are worse [12,41,19]. For instance, if F consists
of spanning trees (bases of a graphic matroid) Goel et al [12] show a lower bound of Ω(n),
while in the case where F corresponds to the
√ cardinality constraint {S : |S| ≥ k} Svitkina
and Fleischer [41] show a lower bound of Ω̃( n). There are a few exceptions. The problem
can be solved exactly when F is a ring family ([40]), triple family ([15]), or parity family
([13]). In the context of NP-Hard problems, there are almost no cases where good (say O(1)

Multi-Agent and Multivariate Submodular Optimization

9

or O(log(n))) approximations exist. We have that the submodular vertex cover admits a
2-approximation ([12,19]), and the k-uniform hitting set has O(k)-approximation.
Multi-agent Problems. In the maximization setting the main multi-agent problem
studied is the Submodular Welfare Maximization (F = {V }) for which the initial 12 approximation [32] was improved to (1 − 1e ) by Vondrak [44] who introduced the continuous
greedy algorithm. This approximation is in fact optimal [21,34]. We are not aware of maximization work for Problem (3) for a nontrivial family F .
For the multi-agent minimization setting, MSCA is the most studied application of Problem (3) (F = {V }). If the functions fi are nonnegative and nonmonotone, [7] recently
showed that no multiplicative factor approximation exists. If the functions can be written
as fi = gi + h for some nonnegative monotone submodular gi and a nonnegative symmetric
submodular function h, a O(log(n)) approximation is given in [3]. In the more general case
where h is nonnegative submodular, a O(k · log(n)) approximation is provided in [7], and
this is tight [35]. For nonnegative monotone functions, MSCA is equivalent to the Submodular Facility Location problem considered in [42], where a tight O(log(n)) approximation is
given.
Goel et al [12] consider the minimization case of (3) for nonnegative monotone submodular functions, in which F is a nontrivial collection of subsets of V (i.e. F ⊂ 2V ) and there is
no restriction on the Fi (i.e. Fi = 2V for all i). In particular, given a graph G they consider
the families of vertex covers, spanning trees, perfect matchings, and shortest st paths. They
provide a tight O(log(n)) approximation for the vertex cover problem, and show polynomial
hardness for the other cases. To the best of our knowledge this is the first time that Problem
(3) has been studied for nontrivial collections F of subsets of V .

2

Generic Multi-agent to Single-agent reduction

In this section, we describe a generic reduction of the capacitated multivariate problem (4)
(and hence (3)) to a single-agent problem. The reduction transforms the solution space into a
lifted space. The new space lives in an associated bipartite graph and facilitates the encoding
of “ownership” in the multi-agent setting. For some special families F , the lifted space has
the same structure and hence the single and multi-agent problems behave similarly (w.r.t.
approximability). The families of forests and matchings are examples of these. We call these
families invariant and discuss them in Section 2.3.
2.1

The Lifting Reduction

In this section we describe a generic reduction of (3) or (4) to a problem of the form
max / min f (S) : S ∈ L
for some function f and family of sets L. This reduction, i.e. the definition of f and L, is
independent of whether we are considering a maximization or minimization problem. The
argument is based on an observation of Nisan et al in [32], where they point out that the
Submodular Welfare Problem (in the setting of combinatorial auctions) is a special case of
submodular maximization subject to a matroid constraint.
Consider the complete bipartite graph G = ([k]+V, E). We think of E as our new ground
set (or lifted space), where an edge (i, v) ∈ E corresponds to assigning item v to agent i.

10

Richard Santiago and F. Bruce Shepherd

Formally, we define a mapping π that identifies the set (2V )k of possible tuples with the set
2E of subsets of edges in the bipartite graph as follows, π : (2V )k → 2E where
]
]
({i} × Si ).
{(i, v) ∈ E : v ∈ Si } =
π(S1 , ..., Sk ) =
i∈[k]

i∈[k]

Now for any S ⊆ E and i ∈ [k], let Si = {v : (i, v) ∈ S}. One now easily checks that π is a
bijection between the above two sets.
Claim. The mapping π is a bijection between (2V )k and 2E with π −1 (S) = (S1 , S2 , . . . , Sk ).
Proof. Clearly π is one-to-one since every set S ∈ 2E (or equivalently S ⊆ E) is written
uniquely as S = ⊎i∈[k] ({i} × Si ). From this we see that π −1 is as claimed.
⊓
⊔
We also see that union and intersection behaves nicely under the mapping π.
Claim. Let S = π(S1 , ..., Sk ) and T = π(T1 , ..., Tk ). Then
S ∪ T = π(S1 ∪ T1 , S2 ∪ T2 , ..., Sk ∪ Tk )

and S ∩ T = π(S1 ∩ T1 , S2 ∩ T2 , ..., Sk ∩ Tk ).

Proof. We show the union identity, the intersection argument being similar.
S ∪ T = π(S1 , ..., Sk ) ∪ π(T1 , ..., Tk )

= (⊎i∈[k] {(i, v) : v ∈ Si }) ∪ (⊎i∈[k] {(i, v) : v ∈ Ti })
= ⊎i∈[k] {(i, v) : v ∈ Si ∪ Ti }

= π(S1 ∪ T1 , S2 ∪ T2 , ..., Sk ∪ Tk ).

⊓
⊔
We can now go from a multivariate function g over V - such as the objectives in (3) and
(4) - to a univariate function in the lifted space. Namely, one defines an associated univariate
function f : 2E → R as follows:
f (S) = g(π −1 (S)), ∀S ⊆ E.
We next give a description of the feasible sets in the lifted space E. We define two families
of sets over E that capture the information of the two constraints in the original class of
problems:
H := {S ⊆ E : S1 + · · · + Sk ∈ F }

and

H′ := {S ⊆ E : Si ∈ Fi , ∀i ∈ [k]}.

Notice that in the definitions of H and H′ we are implicitly using the fact that each S ⊆ E
can be written uniquely as S = ⊎i∈[k] ({i} × Si ) where Si ⊆ V .
Now, it should be clear that with the above definitions of f, H and H′ , we have:
max / min
g(S1 , ..., Sk )
= max / min
f (S)
s.t.
S1 + · · · + Sk ∈ F
s.t.
S ∈ H ∩ H′ .
Si ∈ Fi , ∀i ∈ [k]
Finally, by letting L := H ∩ H′ , our original problem reduces to
max / min f (S) : S ∈ L.

Multi-Agent and Multivariate Submodular Optimization

11

Notice that for the robust problem discussed in Theorem 3 we get
max
min
g(S1 − A1 , . . . , Sk − Ak ) = max min f (S − A).
S1 + · · · + Sk ∈ F PAi ⊆ Si
S∈L A⊆S
|A
|
≤
τ
|A| ≤ τ
Si ∈ F i
i
i
Clearly, this reduction is interesting if our new function f and family of sets L have
properties which allows us to handle them computationally. These properties depend on the
structure of the function g, and the families of sets F and Fi ’s. In the next section we
discuss some properties that are preserved under this reduction.
2.2

Structure and properties preserved

In this section we show that several properties of the original function g and families Fi
and F are preserved under the above reduction. For instance, if the original function g is
(nonnegative, respectively monotone) multivariate submodular, then f is also (nonnegative,
respectively monotone) submodular. Also, if the family F induces a matroid over the original
ground set V , then so does H over the lifted space E. These results are summarized in
the table below. Note that these, combined with the recent advances in SA submodular
optimization (Section 1.4), now imply Theorem 2 and Theorem 3.

MA
SA
1
g multi-submodular
f submodular
2
g monotone
f monotone
3
(V, F) a matroid
(E, H) a matroid
4 (V, F) a p-matroid intersection
(E, H) a p-matroid intersection
5
F = bases of a matroid
H = bases of a matroid
6
F = {V }
H = set of bases of a partition matroid
7
F = 2V
(E, H) a partition matroid
8 (V, Fi ) a matroid for all i ∈ [k]
(E, H′ ) a matroid
9 Fi a ring family for all i ∈ [k]
H′ a ring family

Result
Claim 2.2
Claim 2.2
Lemma 1
Corollary 2
Corollary 3
Claim 2.2
Claim 2.2
Claim 2.2
Claim 2.2

First, we consider which kind of properties our new function f inherits from the function g. The following two claims show that if g is a (nonnegative, respectively monotone)
multivariate submodular function, then f as defined above is (nonnegative, respectively
monotone) submodular.
Claim. The function f defined above is submodular if and only if g is multi-submodular.
Proof. By definition of f and Claim 2.1 we have that for any S = π(S1 , ..., Sk ) and T =
π(T1 , ..., Tk ),
f (S) + f (T ) ≥ f (S ∪ T ) + f (S ∩ T )
m

g(S1 , ..., Sk ) + g(T1 , ..., Tk ) ≥ g(S1 ∪ T1 , ..., Sk ∪ Tk ) + g(S1 ∩ T1 , ..., Sk ∩ Tk ).
The result now follows from the fact that π is a bijection, that is, there is a one-to-one
correspondence between sets S ∈ 2E and tuples (S1 , ..., Sk ) ∈ (2V )k .
⊓
⊔

12

Richard Santiago and F. Bruce Shepherd

Claim. The function f is monotone if and only if g is monotone, and f is nonnegative if
and only if g is nonnegative.
Proof. The latter statement follows directly from the definition of f . The monotonicity
statement follows from noticing that given any two sets S, T ⊆ E, we have that S ⊆ T if
and only if the corresponding tuple of S is contained in the corresponding tuple of T , i.e.,
if and only if (S1 , ..., Sk ) ⊆ (T1 , ..., Tk ).
⊓
⊔
Next, we discuss some properties of F and the Fi ’s that are inherited by H and H′
respectively.
Lemma 1. If (V, F ) is a matroid, then (E, H) is a matroid.
Proof. We check that the two matroid axioms hold for (E, H).
Hereditary property: If T ∈ H and S ⊆ T , then S ∈ H. To see this, let T ∈ H and
and assume S ⊆ T . We know that S and T can be written uniquely as S = ⊎i∈[k] ({i} × Si )
and T = ⊎i∈[k] ({i} × T i ) for some sets Si ’s and T i ’s in V . Since S ⊆ T , we must have that
Si ⊆ T i for each i ∈ [k]. Now, since T ∈ H, we have that Ti ∩ Tj = ∅ for all i 6= j. Hence,
Si ∩ Sj = ∅ for all i 6= j. Also, since T ∈ H, we have that T 1 ∪ ... ∪ T k ∈ F . And given that
S1 ∪ ... ∪ Sk ⊆ T1 ∪ ... ∪ Tk and (V, F ) is a matroid, it follows that S1 ∪ ... ∪ Sk ∈ F . Thus,
S ∈ H.
Greedy property: If S, T ∈ H and |T | > |S|, there exists a ∈ T −S such P
that S +a ∈ H.
Again, let S = ⊎i∈[k] ({i} × Si ) and T = ⊎i∈[k] ({i} × T i ). Notice that |T | = i∈[k] |T i | and
P
|S| = i∈[k] |S i |. Let I = S1 ∪ ... ∪ Sk and J = T1 ∪ ... ∪ T k . Since S, T ∈ H, we know
that I,P
J ∈ F . Also, by theP
disjoint condition on the sets Si ’s and Ti ’s, we have that
|S
|
and
|J|
=
|I| =
i
i∈[k] |T i |. Hence, I, J ∈ F and |J| > |I|. Since (V, F ) is
i∈[k]
a matroid, we know there must exist some b ∈ J − I such that I + b ∈ F . Now, since
b ∈ J, there exists some i0 ∈ [k] such that b ∈ Ti0 , and hence (i0 , b) ∈ T . Also, since
b ∈
/ I, we have that (i0 , b) ∈
/ S. Finally, we show that S + (i0 , b) ∈ H. Observe that
S +(i0 , b) = [⊎i∈[k] ({i}×Si)]+(i0 , b) = [⊎i∈[k]−i0 ({i}×Si )]+({i0 }×Si∗0 ) where Si∗0 = Si0 +b.
We have to show that the sets S1 , ..., Si0 −1 , Si∗0 , Si0 +1 , ..., Sk are pairwise disjoint, and that
their union is an independent set in (V, F ). But the second condition follows directly from
/ I. ⊓
⊔
the fact that (∪i∈[k]−i0 Si ) ∪ Si∗0 = I + b ∈ F , while the first one from the fact that b ∈
Corollary 2. If (V, F ) is a p-matroid intersection, then (E, H) is a p-matroid intersection.
Proof. Let F = ∩pi=1 Ii for some matroids (V, Ii ). Then we have that
H ={S ⊆ E : S1 + · · · + Sk ∈ F }

={S ⊆ E : S1 + · · · + Sk ∈ ∩pi=1 Ii }
={S ⊆ E : S1 + · · · + Sk ∈ Ii , ∀i ∈ [p]}
\
{S ⊆ E : S1 + · · · + Sk ∈ Ii }
=
i∈[p]

=

\

i∈[p]

Ii′ .

Moreover, from Lemma 1 we know that (E, Ii′ ) is a matroid for each i ∈ [p], and the result
follows.
⊓
⊔

Multi-Agent and Multivariate Submodular Optimization

13

Corollary 3. Assume F is the set of bases of some matroid M = (V, I), then H is the set
of bases of some matroid M′ = (E, I ′ ).

Proof. Let F = B(M) and define I ′ = {S ⊆ E : S1 + · · · + Sk ∈ I}. From Lemma 1 we
know that M′ = (E, I ′ ) is a matroid. We show that H = B(M′ ). Let rM and rM′ denote
the rank of M and M′ respectively. Then notice that
H ={S ⊆ E : S1 + · · · + Sk ∈ F }
={S ⊆ E : S1 + · · · + Sk ∈ B(M)}

={S ⊆ E : S1 + · · · + Sk = I ∈ I, |I| = rM }
={S ⊆ E : S1 + · · · + Sk ∈ I, |S| = rM },

where the last equality follows from the fact that |I| = |S1 + · · · + Sk | =
On the other hand we have that

P

i∈[k]

|Si | = |S|.

B(M′ ) ={S ⊆ E : S ∈ I ′ , |S| = rM′ }
={S ⊆ E : S1 + · · · + Sk ∈ I, |S| = rM′ }.

Hence, H = B(M′ ) if and only if rM = rM′ . But notice that for any S ∈ I ′ we have that
|S| = |I| for some I ∈ I, and hence rM′ ≤ rM . Also, for any I ∈ I we can find some S ∈ I ′
(e.g. set S1 = I and Si = ∅ for i 6= 1) such that |S| = |I|, and thus rM′ ≥ rM . It follows
⊓
⊔
that rM = rM′ and hence H = B(M′ ) as we wanted to show.

Claim. Let F = 2V , then H correspond to the family of independent sets of a partition
matroid.
Proof. Assume F = 2V , then

H = {S
= {S
= {S
= {S

⊆E
⊆E
⊆E
⊆E

: S1 + · · · + Sk ∈ 2 V }
: Si ∩ Sj = ∅, ∀i 6= j}
: ∀v ∈ V, |S ∩ δ(v)| ≤ 1}
: ∀v ∈ V, |S ∩ ([k] × {v})| ≤ 1}.

Since {[k] × {v} : v ∈ V } is a partition of E, it follows that (E, H) is a partition matroid
over E.
⊓
⊔

Claim. If F = {V }, then H corresponds to the set of bases of a partition matroid.

Proof. Let F = {V }, then H = {S ⊆ E : S1 + · · · + Sk = V }. From Claim 2.2 we know that
M = (E, I) is a partition matroid over E, where
I := {S ⊆ E : ∀v ∈ V, |S ∩ ([k] × {v})| ≤ 1}.
Moreover, it is easy to see that the set of bases of M corresponds exactly to {S ⊆ E :
S1 + · · · + Sk = V }. Since H = {S ⊆ E : S1 + · · · + Sk = V }, the claim follows.
⊓
⊔
Claim. If (V, Fi ) is a matroid for each i ∈ [k], then (E, H′ ) is also a matroid.

Proof. Let Mi := ({i} × V, Ii ) for i ∈ [k], where Ii := {{i} × S : S ∈ Fi }. Since (V, Fi ) is a
matroid, we have that Mi is also a matroid. Moreover, by taking the matroid union of the
Mi ’s we get (E, H′ ). Hence, (E, H′ ) is a matroid.
⊓
⊔

Claim. If Fi is a ring family over V for each i ∈ [k], then H′ is a ring family over E.
U
U
Proof. Let S, T ∈ H′ and notice that S ∪T = i∈[k] ({i}×(Si ∪Ti )) and S ∩T = i∈[k] ({i}×
(Si ∩Ti )). Since Fi is a ring family for each i ∈ [k], it follows that Si ∪Ti ∈ Fi and Si ∩Ti ∈ Fi
for each i ∈ [k]. Hence S ∪ T ∈ H′ and S ∩ T ∈ H′ , and thus H′ is a ring family over E. ⊓
⊔

14

2.3

Richard Santiago and F. Bruce Shepherd

Invariant families

For a number of families F the approximations factors revealed in [12] are the same for both
the single and multi-agent versions. The lifted space reduction from the previous section is
useful for explaining why this occurs in several cases. In particular, for various families
it turns out that the class F is preserved when performing this reduction. We call these
invariant families (under the above MA to SA reduction). For instance, invariance in the
case of forests could be stated as: if the multivariate problem is defined over the family F of
forests of some graph G, then the reduced (single-agent) version can also be seen as defined
over the family F ′ of forests of some graph G′ . More formally, let E and H be as defined in
the reduction. We say that the class of forests is invariant if: given any graph G and family
F of forests of G, there exists a graph G′ with set of edges E ′ and a bijection π ′ : E → E ′
satisfying that F ′ := {π ′ (S) : S ∈ H} is the family of forests of G′ . We show that forests
(and spanning trees), matchings (and perfect matchings), and st-paths are examples of such
families.
Lemma 2. Given a graph G and a family of sets F over the edges of G, the multi-agent to
single-agent reduction is invariant for the following classes:
(1) Forests
(2) Matchings
(3) st paths
Proof. Let E, H, and π be as defined in the reduction from Section 2. To be consistent with
our previous notation we denote by V the set of edges of G, since this is the ground set of
the original problem. Hence, in this case an element v ∈ V denotes an edge of the original
graph G. The lifting reduction is based on the idea of making k disjoint copies for each
original element, and visualize the new ground set (or lifted space) as edges in a bipartite
graph. However, when the original ground set corresponds to the set of edges of some graph
G, we may just think of the lifted space in this case as being the set of edges of the graph
G′ obtained by taking k disjoint copies of each original edge. We think of choosing the edge
that corresponds to the ith copy of v as assigning element v to agent i. We can formalize
this by defining a mapping π ′ : E → E ′ that takes an edge (i, v) ∈ E to the edge in G′ that
corresponds to the ith copy of edge v in G. It is clear that π ′ is a bijection. Then, via the
bijections π and π ′ we can identify a tuple (S1 , ..., Sk ) with the set of edges in G′ that takes
the first copy of the edges in S1 , the second copies of the edges in S2 , and so on. Now, the
following three statements are straightforward.
(1) Let F be the family of forests of G. Then: (S1 , ..., Sk ) is a feasible tuple for the
original problem (i.e. S1 + · · · + Sk ∈ F ) ⇐⇒ π(S1 , ..., Sk ) ∈ H ⇐⇒ π ′ (π(S1 , ..., Sk ))
induces a forest in G′ .
(2) Let F be the family of matchings in G. Then: (S1 , ..., Sk ) is a feasible tuple for the
original problem ⇐⇒ π(S1 , ..., Sk ) ∈ H ⇐⇒ π ′ (π(S1 , ..., Sk )) induces a matching in G′ .
(3) Let F be the family of st-paths in G. Then: (S1 , ..., Sk ) is a feasible tuple for the
original problem ⇐⇒ π(S1 , ..., Sk ) ∈ H ⇐⇒ π ′ (π(S1 , ..., Sk )) induces an st-path in G′ .
⊓
⊔
Notice that in the proof above π ′ ◦ π is a bijection, and thus the sizes of the sets are
preserved. In particular, given a tuple (S1 , ...Sk ) such that S1 + · · · + Sk = F ∈ F , we have
that |π ′ (π(S1 , ..., Sk ))| = |π(S1 , ..., Sk )| = |F |. This leads to the following corollary.
Corollary 4. Given a graph G, both the families of spanning trees and perfect matchings
of G are invariant under the lifting reduction.

Multi-Agent and Multivariate Submodular Optimization

15

′

In addition, by using the bijection π ′ we can define a function f ′ : 2E → R as f ′ (S ′ ) =
f (π ′−1 (S ′ )). It is clear that f ′ inherits all the properties (e.g. nonnegativity, monotonicity,
submodularity, etc) of f . Then, we have the following:
min
g(S1 , ..., Sk )
= min f (S) = min f ′ (S ′ )
s.t. S1 + · · · + Sk ∈ F
s.t. S ∈ H
s.t. S ′ ∈ F ′ ,
where F ′ = {π ′ (S) : S ∈ H}. Moreover, from Lemma 2 and Corollary 4 we have that F and
F ′ are of the same class in the cases where F are forests, spanning trees, matchings, perfect
matchings, and st-paths.
The following result describes the algorithmic consequences of Lemma 2 and Corollary
4.
Corollary 5. The SA and MV problems for the structures described in Lemma 2 and Corollary 4 are equivalent, in the sense that approximation factors and hardness results are the
same for the SA and MV versions of the problem.
Proof. It follows from the fact that approximation factors and hardness results for the above
combinatorial structures only depend on the number of nodes (and not on the number of
edges) of the underlying graph. Given that the number of nodes remain invariant under
taking k disjoint copies of each edge, the result follows.
⊓
⊔
2.4

Invariance of multivariate rings

In this section we focus on the class of problems
min / max g(S1 , ..., Sk )
s.t.
(S1 , ..., Sk ) ∈ D,
where D ⊆ (2V )k . Notice that this is a much more general framework than the CMVSO
class of problems defined in (4). In general, one would not expect to have much tractability
for these kind of problems even when both the objective function and the feasible space
have some structure. In this section we show that the generic reduction from Section 2
allows us to solve the above problem exactly in the minimization setting when the objective
function g is an arbitrary multivariate submodular function and the feasible space D has a
ring like structure (that is, closed under unions and intersections). Formally, we say that a
family of tuples D is a multivariate ring if for any two tuples (S1 , ..., Sk ), (T1 , ..., Tk ) ∈ D the
coordinate-wise union and intersection (i.e. (S1 ∪T1 , S2 ∪T2 , ..., Sk ∪Tk ) and (S1 ∩T1 , ...., Sk ∩
Tk )) also belong to D. The following result shows that the ring like structure is preserved
under the reduction.
Lemma 3. Let E and π be as defined in the reduction of Section 2. Then, if D is a multivariate ring, the family D′ := {π(S1 , ..., Sk ) : (S1 , ..., Sk ) ∈ D} is a ring over E.
Proof. Let S, T ∈ D′ . Let (S1 , ..., Sk ), (T1 , ..., Tk ) ∈ D be such that S = π(S1 , ...., Sk ) and
T = π(T1 , ..., Tk ). We have to show S ∪ T, S ∩ T ∈ D′ . From Claim 2.1 we know that
S ∪ T = π(S1 ∪ T1 , S2 ∪ T2 , ..., Sk ∪ Tk ) and S ∩ T = π(S1 ∩ T1 , ..., Sk ∩ Tk ). Now the result
follows from the fact that (S1 ∪ T1 , ..., Sk ∪ Tk ), (S1 ∩ T1 , ..., Sk ∩ Tk ) ∈ D by definition of
multivariate ring.
⊓
⊔

16

Richard Santiago and F. Bruce Shepherd

Now, it follows from the reduction that
min g(S1 , ..., Sk ) = min f (S)
s.t. (S1 , ..., Sk ) ∈ D
s.t. S ∈ D′ ,
where if D is multivariate ring then D′ is a ring, and if g is an arbitrary multivariate submodular function then f is an arbitrary submodular function. Hence, given that minimization
of a submodular function over a ring family can be done efficiently ([38,40]), we have the
following result.
Lemma 4. The problem
min g(S1 , ..., Sk ) : (S1 , ..., Sk ) ∈ D
where D is a multivariate ring family and g is an arbitrary multivariate submodular function
can be solved exactly in polynomial time.

3

Reductions for Multi-Agent and Multivariate Minimization

In this section we seek a generic reduction of a multi-agent (and some times multivariate)
minimization problem to its single-agent primitive. We develop this method in the case
where the objective function is nonnegative monotone (multivariate) submodular and we
work with the natural LP formulation (cf. Appendix A). Specifically we prove the following.
Theorem 6. Suppose there is a (polytime) α(n)-approximation for the single-agent nonnegative monotone submodular minimization problem based on rounding the natural LP
for a family F . Then there is a (polytime) O(α(n) · min{k, log2 (n)})-approximation for the
multi-agent nonnegative monotone submodular minimization problem over F . Moreover, the
O(kα(n))-approximation extends to the more general multivariate setting.
We note that the log2 (n) approximation loss due to having multiple agents is in the right
ballpark. This is because for the vertex cover problem there is a factor 2-approximation for
single-agent submodular minimization, and a (tight) O(log(n))-approximation for the multiagent version [12].
3.1

The Single-Agent and Multi-Agent Formulations

Due to monotonicity, one may often assume that we are working with a family F which
is upwards-closed, aka a blocking family. The advantage is that to certify whether F ∈ F ,
we only need to check that F ∩ B 6= ∅ for each element B of the family B(F ) of minimal
blockers of F . We discuss the details in Appendix A. This gives rise to the natural blocking
LP formulation for the single-agent and multi-agent problems as used in [12]. These are
discussed in detail in Appendix B. The single-agent LP is:
P
f (S)x(S)
min
P
P S⊆V
(5)
x(S)
≥ 1, ∀B ∈ B(F )
s.t.
v∈B
S∋v
x(S) ≥ 0,
and the corresponding dual is given by

Multi-Agent and Multivariate Submodular Optimization

17

P
max
B∈B(F ) yB
P
P
s.t.
v∈S
B∋v yB ≤ f (S), ∀S ⊆ V
yB ≥ 0.

(6)

P
P
f (S)x(S, i)
min
P
P S⊆V
P i∈[k] i
s.t. v∈B S∋v i∈[k] x(S, i) ≥ 1, ∀B ∈ B(F )
x(S, i) ≥ 0,

(7)

P
max
B∈B(F ) yB
P
P
y
≤
fi (S), ∀i ∈ [k], ∀S ⊆ V
s.t.
v∈S
B∋v B
yB ≥ 0.

(8)

The multi-agent LP is:

and its dual is:

By standard methods (see Appendix B) one may solve these problems exactly in polytime
if one can separate over the blocking formulation P ∗ (F ) := {z ≥ 0 : z(B) ≥ 1 for all B ∈ B(F )}.
This is often the case for many natural families such as spanning trees, perfect matchings, st-paths, and vertex
Pcovers.
P For any feasible solution x to (7) we associate a vector
z : V → R+ by z(v) := S∋v i∈[k] x(S, i). Note that feasibility of x is equivalent to the
condition z ∈ P ∗ (F ). In the following we work with the extended vectors (x, z).
3.2

A Multi-Agent O(α(n) log2 (n)) − approximation

While the proof of this result uses several standard pre-processing ingredients, it also requires
some new techniques to deal with submodular objectives (these would not be necessary for
a multi-agent problem with linear (modular) objectives). We also need the submodularity
of a particular set function which arises from a partition U1 , U2 , . . . , Uk of a ground set
V . Suppose we are given such sets with arbitrary costs c(Ui ). We define a set function
g : 2V → R where g(∅) = 0 and for any non-empty set S:
X
c(Ui ).
g(S) =
i:S∩Ui 6=∅

Proposition 2. The function g(S) is submodular and monotone if the c(Ui ) are nonnegative.
Proof. We establish the diminishing returns property of g. Let A ⊆ B and v ∈ V − B.
Suppose that g(B + v) − g(B) > 0. This means that v ∈ Ui such that B ∩ Ui = ∅. But then
A ∩ Ui = ∅ as well, and so g(A + v) − g(A) = c(Ui ) = g(B + v) − g(B).
⊓
⊔
Theorem 7. Suppose there is a (polytime) α(n)-approximation for the single-agent nonnegative monotone submodular minimization problem based on rounding the natural LP for
a family F . Then there is a (polytime) O(α(n) log 2 (n))-approximation for the multi-agent
nonnegative monotone submodular minimization problem over F .
Proof. Let (x∗ , z ∗ ) denote an optimal solution to the multi-agent LP associated with F and
the fi ’s. As discussed in Appendix B.4, this can be found in polytime under fairly mild
assumptions. In order to apply a black box single-agent rounding algorithm we must create

18

Richard Santiago and F. Bruce Shepherd

a different multi-agent solution. This is done in several steps, the first few of which are
standard. The key steps are the fracture, expand and return steps which arise later in the
process.
P
1
. Note that v small z ∗ (v) ≤ 21 , and so for any
Call an element v small if z ∗ (v) ≤ 2n
blocking set B ∈ B(F ), we have that at most 12 of z ∗ (B) is contributed by small elements.
Let S − denote the set obtained after removing all small elements from S. Then for any
B ∈ B(F ) we have z ∗ (B − ) ≥ 12 . So let us consider dropping all small v by removing them
from sets in the support and then doubling the resulting sets. That is, we obtain a new
solution (x′ , z ′ ) by starting with x′ ≡ x∗ and then doing the following for each (S, i) in the
support of x∗ . Reduce x′ (S, i) by x∗ (S, i) and then increase x′ (S − , i) by the amount 2x∗ (S, i).
As fi ’s are monotone, this at most doubles the cost of the original solution (x∗ , z ∗ ).
We now prune the solution (x′ , z ′ ) a bit more. Let Zj be the elements v such that
1
′
z (v) ∈ (2−(j+1) , 2−j ] for j = 0, 1, 2, . . . , L. Since z ′ (v) > 2n
for any element in the support,
we have that L ≤ log(n). We call Zj bin j and define rj = 2j . We round up each v ∈ Zj
so that z ′ (v) = 2−j by augmenting the x′ values by at most a factor of 2. We may do this
simultaneously for all v by possibly “truncating” some of the sets involved, i.e., changing
some x′ (S, i) values to be x′ (T, i) where T ⊆ S. As before, this is fine since fi ’s are monotone.
In the end, we call this a uniform solution (x′′ , z ′′ ) in the sense that each z ′′ (v) is some power
of 2. Note that its cost is at most a constant factor times the original MA LP solution.
Fracture. We now create another fractured solution (x′′′ , z ′′′ ) as follows. For each
support variable x′′ (S, i) > 0, we replace this variable by several variables, one for each set
Sj = S ∩ Zj with j = 0, 1, 2, ...L. Set x′′′ (Sj , i) = x′′ (S, i) for each j. By monotonicity we
have that fi (Sj ) ≤ fi (S) and so the cost of this solution goes up by a factor of at most
L ≤ log(n). Note that z ′′′ = z ′′ .
Expand. Now for any S ⊆ Zj with x′′′ (S, i) > 0 for some i, we blow it up by a factor
rj . (Don’t worry, this scaling is temporary.) Since z ′′′ (v) = r1j for each v ∈ Zj , this means
that the resulting values yield a (probably fractional) cover of Zj . At this point, we are
completely ignoring submodularity - we simply have sets with costs: e.g., for set S above we
have c(S) = fi (S). By standard greedy, we then turn this fractional cover into an integral
cover of Zj by increasing the cost by a factor of at most ln(n). Moreover, we may again use
monotonicity to truncate some of the sets so that our cover consists of disjoint sets. So let
U1j , U2j , . . . Un(j)j be the corresponding partition of Zj .
Return. Now we go back to get a new MA LP solution (x̂, ẑ) whose support is on
disjoint sets. For each Usj we re-set x̂(Usj , i) = r1j where i was the agent associated with
the set Usj . Note that ẑ = z ′′′ and so this is indeed feasible (and again uniform).
Single-Agent Rounding. In the last step, we show that we may use Proposition 2
to apply single-agent submodular rounding to produce a provably “good” solution for the
multi-agent problem.
We define the submodular function g on V induced by the disjoint sets Usj and their
costs which are inherited from various agents. We may then consider an associated singleagent submodular optimization problem min g(S) : S ∈ F . Clearly the multi-agent solution
(x̂, ẑ) induces a solution (y, ẑ) for this single-agent problem as well. Namely y has a support
{Usj } and y(Usj ) = x̂(Usj , i), where i is the agent associated to Usj . Moreover, by definition
of g(), the cost of this solution is the same as for (x̂, ẑ).
Now suppose we have an α-approximation for submodular optimization over the natural
formulation P ∗ (F ), and so we can produce an integral solution whose cost is at most α
times the cost of (y, ẑ) which in turn costs at most O(log2 (n)) ma-lp. (We paid a factor
O(log n) for fracturing, and a factor O(ln n) for greedy set cover.) But an integral solution

Multi-Agent and Multivariate Submodular Optimization

19

for this single-agent problem is effectively picking off some of the sets Usj ’s, and the price
we pay for any such set is the same as the associated agent’s cost in the original MA
optimization problem. If some agent i ends up picking several Usj ’s we may combine them
due to subaddivity of fi . In other words, we now have a feasible solution for the multiagent problem whose cost is at most O(αlog 2 (n)) times the original LP. This completes the
description of the algorithm.
⊓
⊔
3.3

A Multivariate O(kα(n)) − approximation

In this section we consider the more general multivariate class of problems
(MV)

min g(S1 , . . . , Sk ) : S1 + · · · + Sk ∈ F ,

(9)

where g is a nonnegative monotone multivariate submodular function. As shown in Proposition 1, this class encodes much more than their decomposable counterparts.
We use the generic reduction from Section 2 to obtain a Single-agent Reduced (SAR)
problem
(SAR) min f (S) : S ∈ H.
(10)
Let G = ([k] + V, E) denote the underlying bipartite graph. Recall that S ⊆ E(G) lies in H
if and only if cov(S) ∈ F and |S ∩ δG (v)| ≤ 1 ∀v ∈ V . Recall also that if g is nonnegative
monotone multivariate submodular, then f is nonnegative monotone submodular (see Claims
2.2 and 2.2).
We first show that under mild assumptions we can solve in polytime the single-agent LP
associated to (10).
Claim. If we can separate in polytime over P ∗ (F ), then we can solve in polytime the singleagent LP associated to (10).
Proof. First notice that the blocking sets of H are just B(H) = {∪v∈B δG (v) : B ∈ B(F )}.
Then observe that
′
′
P ∗ (H) = {w ∈ RE
+ : w(B ) ≥ 1, ∀B ∈ B(H)}

= {w ∈ RE
+ : w(∪v∈B δG (v)) ≥ 1, ∀B ∈ B(F )}
X
= {w ∈ RE
w(δG (v)) ≥ 1, ∀B ∈ B(F )}.
+ :
v∈B

V
Now, given any vector w ∈ RE
+ we can associate a vector z ∈ R+ defined by z(v) =
w(δG (v)). Then, it is clear that for each B ∈ B(F ) we have

z(B) ≥ 1 ⇐⇒

X

v∈B

w(δG (v)) ≥ 1.

Hence, w ∈ P ∗ (H) if and only if z ∈ P ∗ (F ). Given that we can separate in polytime over
P ∗ (F ), it follows that we can also separate in polytime over P ∗ (H). Hence we can solve the
LP associated to (10) in polytime.
⊓
⊔
We now prove the main result of this section. The proof combines the machinery from
the reduction of Section 2 and some of the methods from Section 3.1.

20

Richard Santiago and F. Bruce Shepherd

Theorem 8. Suppose there is a (polytime) α(n)-approximation for the single-agent nonnegative monotone submodular minimization problem based on rounding the natural LP for
a family F . Then there is a (polytime) O(kα(n))-approximation for the multivariate nonnegative monotone submodular minimization problem over F .
Proof. Consider the multivariate problem over F given by (9) and apply the generic reduction from Section 2 to get a single-agent problem over the lifted space as given by (10). Let
OPT(MV) denote the value of the optimal solution to (9). Also, let OPT(SAR) denote the
value of the optimal solution to (10), and OPT(SAR-LP) the value of the optimal solution
to the LP associated with (10). Since (9) and (10) are equivalent, it is clear that
OP T (SAR-LP) ≤ OP T (SAR) = OP T (MV).
We construct a new single-agent minimization problem:
(NEW-SA)

min f ′ (S) : S ∈ F

where f ′ : 2V → R+ is nonnegative monotone submodular. It’s blocking LP relaxation
also satisfies OP T (NEW-LP) ≤ k · OP T (MV). In addition, each feasible solution F ∈ F for
(NEW-SA) induces a feasible solution S1 +· · ·+Sk = F for the original multivariate problem
(MV) of the same objective value. Then the desired result follows from the (polytime) α(n)approximation assumption, since then we can find F ∗ ∈ F such that F ∗ = S1∗ + · · · + Sk∗
and
g(S1∗ , . . . , Sk∗ ) = f ′ (F ∗ ) ≤ α · OP T (NEW-LP) ≤ αk · OP T (MV).
We construct the function f ′ as follows. Let y ∗ (S) be an optimal solution for the singleagent LP associated to (10). Since y ∗ is feasible for the LP, we must have
XX
e∈B ′ S∋e

y ∗ (S) ≥ 1, ∀B ′ ∈ B(H).

Equivalently, since B(H) = {∪v∈B δG (v) : B ∈ B(F )}, the feasibility condition can be also
stated as
X X X
y ∗ (S) ≥ 1, ∀B ∈ B(F ).
v∈B e∈δG (v) S∋e

=
P For any feasible solution y to (10) we associate a vector w : E → ∗R+ by w(e)
∗
y(S).
Note
that
feasibility
of
y
is
equivalent
to
the
condition
w
∈
P
(H).
Let
w
be
S∋e
the vector associated to the optimal solution y ∗ . Moreover, for each vj ∈ V let e∗j be the
edge in the bipartite graph G satisfying
w∗ (e∗j ) = max w∗ (e) = max w∗ (i, vj ),
e∈δG (vj )

i∈[k]

and let T ∗ = {e∗1 , e∗2 , . . . , e∗n }. Also, for any set S ⊆ E, let S − denote the set obtained after
removing all elements of E − T ∗ from S.
So let us consider dropping all elements from E − T ∗ by removing them from sets in
the support and then increasing by a factor of k the resulting sets. That is, we obtain a
new solution y ′ by starting with y ′ ≡ y ∗ and then doing the following for each S in the
support of y ∗ . Reduce y ′ (S) by y ∗ (S) and then increase y ′ (S − ) by the amount ky ∗ (S). As

Multi-Agent and Multivariate Submodular Optimization

21

f is monotone, this increases the cost of the original solution y ∗ by at most a factor of k.
Notice that feasibility of y ′ follows by observing that for each B ∈ B(F ) we have that

X

X X

X X

y ′ (S) =

y ′ (S) =

vj ∈B S∋e∗
j

vj ∈B e∈δ(vj ) S∋e

X X

vj ∈B S∋e∗
j

ky ∗ (S) ≥

X

X X

vj ∈B e∈δ(vj ) S∋e

y ∗ (S) ≥ 1.

Let π : V → T ∗ be the natural bijection between V and T ∗ where π(vj ) = e∗j . Notice
that for any set S ⊆ V we have that cov(π(S)) = S and |π(S) ∩ δG (v)| ≤ 1 ∀v ∈ V . Hence
F ∈ F ⇐⇒ π(F ) ∈ H|T ∗ .
Thus, any feasible solution F ∈ F induces (via the bijection π) a feasible solution for (SAR),
which in turn induces (via the generic reduction from Section 2) a feasible solution for (MV).
Consider the function f ′ : 2V → R+ defined as f ′ (S) = f (π(S)). The right hand side is
just the restriction f |T ∗ of f to T ∗ and hence it is again nonnegative monotone submodular.
Since π is a bijection, f ′ is as well. Moreover, notice that for any F ∈ F we have (by
definition of f ′ ) that f ′ (F ) = f (π(F )), and hence
min f ′ (S) : S ∈ F = min f (S) : S ∈ H|T ∗ .
In addition, F ∗ ∈ F is an optimal solution for min f ′ (S) : S ∈ F if and only if π(F ∗ ) is an
optimal solution for min f (S) : S ∈ H|T ∗ .
We now consider the new single-agent problem min f ′ (S) : S ∈ F and its associated LP
given by:
P
f ′ (S)x(S)
min
P
P S⊆V
(11)
(NEW-LP) s.t.
v∈B
S∋v x(S) ≥ 1, ∀B ∈ B(F )
x(S) ≥ 0.

We construct a feasible solution x′ for (11) by setting x′ (S) = y ′ (π(S)) for each S ⊆ V .
Or equivalently, for each S ⊆ E in the support of y ′ set x′ (π −1 (S)) = y ′ (S), and set
x′ (π −1 (S)) = 0 for each S ⊆ E not in the support. Notice that feasibility of x′ for (11) now
comes from the feasibility of y ′ for the LP associated to (10), since for any B ∈ B(F ) we
have
X X
X X
X X
x′ (S) =
y ′ (π(S)) =
y ′ (S) ≥ 1.
vj ∈B S∋vj

vj ∈B S∋e∗
j

vj ∈B S∋vj

Moreover, we have that the objective value associated to the solution x′ satisfies
X
X
X
f ′ (S)x′ (S) =
f (π(S))y ′ (π(S)) =
f (S)y ′ (S) ≤ k · OP T (SAR-LP),
S⊆V

S⊆V

S⊆E

and hence
OP T (NEW-LP) ≤ k · OP T (SAR-LP) ≤ k · OP T (MV)
as we wanted to show.
⊓
⊔
The above theorem has many interesting consequences. We now discuss one that leads to
a polytime k-approximation for the submodular facility location problem, where k denotes
the number of facilities.

22

Richard Santiago and F. Bruce Shepherd

Corollary 6. Let f be a nonnegative monotone multivariate submodular function on V .
Then there is a polytime k-approximation for
min
f (S1 , ..., Sk )
s.t. S1 + · · · + Sk = V.
Proof. Notice that the single-agent version of the above multivariate problem is the trivial
min f (S) : S ∈ {V }. Hence a polytime exact algorithm is available for the single-agent
problem and thus a polytime k-approximation is available for the multivariate version. ⊓
⊔
P
A very special case of Corollary 6 occurs when f (S1 , ..., Sk ) = i∈[k] fi (Si ) for some nonnegative monotone submodular fi ’s. This is equivalent to the submodular facility location
problem considered by Sviktina and Tardos in [42], where they give a tight O(ln(n)) approximation. Their approximation is in terms of n, which in this setting denotes the number of
customers/clients/demands. Notice that from Corollary 6 we can immediately provide an
approximation in terms of the number of facilities. This bound clearly becomes preferable
in facility location problems (for instance, Amazon) where the number of customers swamps
the number of facility locations (i.e. n >> k).
Corollary 7. There is a polytime k-approximation for submodular facility location, where
k denotes the number of facilities.

4

Bounded Blockers and Submodular Minimization

Many natural classes F have been shown to behave poorly for (nonnegative, monotone)
submodular minimization. For instance, polynomial inapproximability has been established
in the case where
√ F is the family of edge covers ([19]), spanning trees ([12]), or perhaps most
damning is Ω̃( n)-inapproximability for minimizing f (S) subject to the simple cardinality
constraint |S| ≥ k 4 [41]. These results all show that it is difficult to distinguish between
two similar submodular functions, one of which “hides” the optimal set. At some level, the
proofs leverage the fact that f can have wild (so-called) curvature [6].
A few cases exist where good approximations hold. For instance, for ring families the
problem can be solved exactly by adapting any algorithm that works for unconstrained
submodular minimization ([38,40]). Grötschel, Lovász, and Schrijver ([15]) show that the
problem can be also solved exactly when F is a triple family. Examples of these kind of
families include the family of all sets of odd cardinality, the family of all sets of even cardinality, or the family of sets having odd intersection with a fixed T ⊆ V . More generally,
Goemans and Ramakrishnan ([13]) extend this last result by showing that the problem
can be solved exactly when F is a parity family (a more general class of families). In the
context of NP-Hard problems, the cases in which a good (say O(1) or O(log(n))) approximation exists are almost non-existent. We have that the submodular vertex cover admits
a 2-approximation ([12,19]), and the k-uniform hitting set has O(k)-approximation. It is
natural to examine the core reasons why these approximations algorithms work in the hope
of harnessing ingredients in other contexts of interest.
We emphasize that our work in this section focuses only on nonnegative normalized
monotone functions. We also restrict attention to upwards-closed families F , that is, if
F ⊆ F ′ and F ∈ F , then F ′ ∈ F . Due to monotonicity this is usually a benign assumption
4

which is equivalent to the constraint |S| = k since f is monotone

Multi-Agent and Multivariate Submodular Optimization

23

(see Appendix A). For instance, if we have a well-described formulation (or approximation)
for the polytope P (F ) whose vertices are {χF : F ∈ F }, then we can also separate over its
upwards closure P (F )↑ := {z ≥ x : x ∈ P }. A second issue one must address when working
with the upwards-closure of a family F is whether, given F ′ in the closure, one may find a
set F ∈ F with F ⊆ F ′ in polytime. This is also the case if a polytime separation oracle is
available for P (F ).
4.1

Bounded Blockers and Single-Agent Minimization

Algorithms for vertex cover and k-uniform hitting sets rely only on the fact that the feasible
space has a bounded blocker property. We call a clutter (set family) F β-bounded if |F | ≤ β
for all F ∈ F .
The next result is the main algorithmic device of this section and has several natural
applications including implications for the class of multi-agent problems over F . These are
discussed in the following sections.
Theorem 9. Consider the (nonnegative, normalized, monotone) submodular minimization
primitive
min f (S) : S ∈ F
and its natural LP (5). If B(F ) is β-bounded, then (5) has integrality gap of at most β.

∗
Proof. Now assume we have that xP
is an optimal solution for the primal (5) with value
opt. We claim that Q = {v ∈ V : S:S∋v x∗ (S) ≥ β1 } is an β-approximation. Recall that
Q ∈ F if and only if Q ∩ B 6= ∅ for each
B(F ). Pick an arbitrary B ∈ B(F ), since x∗ is
P B ∈P
a feasible solution P
we must have that v∈B S∋v x∗ (S) ≥ 1. Hence, there must exist some
1
v0 ∈ B such that S∋v0 x∗ (S) ≥ |B|
≥ β1 , where the last inequality follows from the fact
that B(F ) is β-bounded. It follows that v0 ∈ Q and thus Q ∩ B ⊇ {v0 } =
6 ∅. Since βx∗ is
a fractional cover of Q, we may now apply Corollary 13 (the latter part in particular) to
deduce that f (Q) ≤ β opt.
⊓
⊔

In many circumstances this result becomes algorithmic. For instance, as discussed in
Lemma 11 in Appendix B.2 we have the following.
Corollary 8. If B(F ) is β-bounded and |B(F )| ∈ poly(n), then there is a polytime βapproximation for (5). This is the case in particular if β = O(1).
We note that it is not necessary to have a O(1)-bounded blocker to derive an O(1)approximation algorithm; for instance we could have that F is polynomially bounded in
some cases so an exact algorithm exists. The inapproximability result of Khot et al. [22]
could be seen as a type of converse to Theorem 9; it suggests that if the blockers are large,
and suitably rich, then submodular minimization over F is doomed.
Theorem 10 (Khot, Regev [22]). Assuming the Unique Games conjecture, there is a
(k − ǫ)-inapproximability factor for the problem of finding a minimum size vertex cover in
a k-uniform hypergraph.
The restriction that |B(F )| ∈ poly(n) could be quite severe. In Appendix B.3 we discuss
how LP (5) can still be solved in polytime under a much weaker assumption. In particular
we show the following.
Corollary 9. Assume there is a polytime separation oracle for the blocking formulation
P ∗ (F ). Then LP (5) can be solved in polytime.

24

4.2

Richard Santiago and F. Bruce Shepherd

Applications of Bounded Blockers

We discuss several problems which can be addressed by bounded blockers. We start with
some of the simplest examples which also indicate how one might find uses for Theorem 9.
We later discuss applications to multi-agent minimization.
Example 8 (Edge Covers). Let G = (V, E) be an undirected graph and F denote the
family of edge covers of G. It follows that B(F ) consists of the n sets δ(v) for each v ∈ V .
Theorem 9 immediately implies that that the minimum submodular edge cover problem is ∆approximable for graphs of max degree ∆. In particular, the Ω(n/log(n)) inapproximability
result from [19] is pinpointed on graphs with at least one high-degree node.
This example is not surprising but gives clarity to the message that whenever the blocker
B(F ) induces a bounded-degree hypergraph, Theorem 9 applies. Let’s explore a few questions which can be approached like this. In [42] an O(ln n)-approximation is given for submodular facility location, but for instances where the number of customers n dwarfs the
number of facilities k the following is relevant.
Example 9 (Facility Location). Suppose we have a submodular facility location problem
with k facilities and n customers. We may represent solutions as subsets of edges in a k × n
bipartite graph G which include exactly one edge incident to each customer node. As our
submodular functions are monotone, we can work with the associated blocking family F for
which B(F ) consists of the edges δG (v), where v is a customer node. A k-approximation now
follows from Theorem 9.
We consider the several examples from the broad task of finding low-cost dense networks.
Example 10 (Lightly Pruned Networks). Suppose we seek low-cost subgraphs of some
graph G where nodes can only have a limited number τ of their edges removed. In other
words, the degree of each node v should remain at least deg(v) − τ . The family of subgraphs
(viewed as edge subsets) F has as its blocker the set of all sub-stars of size τ + 1: B(F ) =
{E ′ ⊆ δ(v) : |E ′ | = τ + 1, v ∈ V (G)}. When τ is small (constant or polylog) one obtains
sensible approximations. This can be extended to notions of density which incorporate some
tractable family of cuts δ(S) ∈ C. That is, where the designed subgraph must retain all but a
bounded number τ of edges from each δ(S).
Example 11 (Girth-Widening). For an undirected graph G we seek to minimize f (J)
where J is subset of edges for which G − J does not have any short cycles. For instance,
given a threshold τ we want G−J to not have any cycles of length at most τ . We seek J ∈ F
whose blocker consists of all cycles with at most τ edges. The separation can be solved in this
setting since constrained shortest paths has a polytime algorithm if one of the two metrics
is unit-cost.
Decomposing (or clustering) graphs into lower diameter subgraphs is a scheme which occasionally arises (for instance, the tree-embedding work of [8] employs a diameter-reduction
step). We close with an example in this general vein.
Example 12 (Diameter-Reduction). Suppose we would like to find a submodular-sparse
cut in a graph G which decomposes it into subgraphs G1 , G2 , . . . each of which has a bounded
diameter τ . We are then looking at a submodular minimization problem whose bounded
blocker consists of paths of length exactly τ + 1.

Multi-Agent and Multivariate Submodular Optimization

4.3

25

Bounded Blockers and Multi-Agent Minimization

In this section we establish an O(β ln(n))-approximation for the nonnegative monotone
multi-agent submodular problem associated to families with β-bounded blockers. Notice
that this result generalizes the 2 ln(n)-approximation for multi-agent vertex cover (Goel et
al [12]).
Theorem 11. Let F be a family with a β-bounded blocker. Then there is a β ln(n)-approximation
algorithm for the associated multi-agent nonnegative monotone problem. If P ∗ (F ) has a
polytime separation oracle, then this is a polytime algorithm.
Proof. Let x∗ be an optimal solution to (7). Recall that if P ∗ (F ) has a polytime separation
oracle then weP
have P
that x∗ can be computed in polynomial time (Corollary 9). Consider
Q = {v ∈ V : S∋v i∈[k] x∗ (S, i) ≥ β1 }. Since F has a β-bounded blocker it follows that
P P
Q ∈ F , and moreover, βx∗ is a fractional cover of Q. That is, S i βx∗ (S, i)χS ≥ χQ .
We now appeal to standard analysis of the greedy algorithm applied to the fractional set
cover (of Q) with set costs given by c((S, i)) = fi (S). This results in an integral cover
of Q whose cost is augmented by a factor of at most ln n times the fractional cover.
Denote
integral cover by (S 1 , 1), ..., (S m1 , 1), (S 1 , 2), . . . , (S m2 , 2), ..., (S mk , k). Since
P P this
∗
S
i x (S, i)fi (S) ≤ OP T (M A) we have that the integral cover cost satisfies
mi
k X
X
i=1 j=1

c(S j , i) ≤ ln(n)

XX
i

S

= β ln(n)

βx∗ (S, i)fi (S)

XX
S

x∗ (S, i)fi (S)

i

≤ β ln(n)OP T (M A).
j
i
In addition, by letting Si = ∪m
j=1 (S , i), by submodularity (or just subadditivity) we have
k
X

fi (Si ) =

i=1

k
X
i=1

j
i
fi (∪m
j=1 (S , i)) ≤

k X
mi
X

fi ((S j , i)) =

i=1 j=1

k X
mi
X

c(S j , i).

i=1 j=1

Finally, if Si ∩ Sj 6= ∅ for some i 6= j throw away the common shared elements from
one of them arbitrarily. Denote by S1∗ ,...,Sk∗ these new sets, and notice that Si∗ ⊆ Si and
S1∗ + ... + Sk∗ = Q. By monotonicity of the functions fi ’s we have
X
X
fi (Si ) ≤ β ln(n)OP T (M A)
fi (Si∗ ) ≤
i∈[k]

i∈[k]

and the result follows.

5

⊓
⊔

Multi-agent minimization over F = {V }

In this section we discuss the multi-agent framework (3) in the minimization setting and in
the special case where the functions fi are nonnegative and F = {V }. That is, we focus on
the problem
Pk
min
i=1 fi (Si )
s.t. S1 + · · · + Sk = V
Si ∈ Fi , ∀i ∈ [k]

26

Richard Santiago and F. Bruce Shepherd

where the functions fi are nonnegative submodular.
As previously discussed in Section 1.2 (see Example 5), the special case of this problem
where the agents are allowed to take any subset of V (i.e. Fi = 2V for all i) has been widely
considered in the literature and it has been referred to as the Minimum Submodular Cost
Allocation (MSCA) problem. We summarize the results for MSCA here.
Theorem 12. Consider MSCA for nonnegative functions fi . We have the following.
1. There is a polytime (tight) O(ln(n))-approx for the case where the functions are monotone ([17,42]).
2. There is a polytime (tight) O(ln(n))-approx for the case where the functions fi can be
written as fi = gi + h for some nonnegative monotone submodular gi and a nonnegative
symmetric submodular function h ([3]).
3. There is a polytime (tight) O(k · ln(n))-approx for the case where the functions fi can be
written as fi = gi + h for some nonnegative monotone submodular gi and a nonnegative
submodular function h ([7,35]).
4. For general functions fi and k ≥ 3 this problem does not admit any finite multiplicative
approximation factor ([7]).
We now discuss the monotone MSCA problem with additional constraints on the sets that
the agents can take. Two of the most natural settings to consider are to impose cardinality
constraints on the number of elements that an agent can take, or to allow agent i to only
take elements from some subset Vi ⊆ V , or both. The rest of this section will be dealing
with multi-agent problems that incorporate one (or both) of such constraints. We use one
of these problems to provide an example of an instance in which the multivariate problem is
Ω(n) hard to approximate while its “decomposable” version (i.e. MA) can be solved exactly
(see Corollary 11 and Lemma 6).
The following result is an observation that derives from the work of Svitkina-Tardos [42]
on the submodular facility location problem.
Corollary 10. The problem

Pk
min
i=1 fi (Si )
s.t. S1 + · · · + Sk = V
Si ⊆ Vi ,

where the functions fi are nonnegative monotone submodular admits a ln(maxi∈[k] |Vi |)approximation.
Proof. Svitkina-Tardos [42] provide a reduction of the problem
Pk
min
i=1 fi (Si )
s.t. S1 + · · · + Sk = V
where the functions fi are nonnegative monotone submodular to a set cover instance. Then,
the greedy algorithm (using unconstrained submodular minimization as a subroutine) is
used to obtain an optimal ln(n)-approximation. The same reduction applied in this setting
gives a t-set cover instance (i.e. an instance where all the sets have size at most t) with
t = maxi∈[k] |Vi |. Now the result follows from the fact that greedy gives a ln(t)-approximation
for the t-set cover problem.
⊓
⊔

Multi-Agent and Multivariate Submodular Optimization

27

We now consider the above problem with an additional cardinality constraint on the
sets the agents can take. We use the techniques from the generic reduction presented in
Section 2 and a known result from matching theory in bipartite graphs to obtain the desired
approximation. We first introduce some definitions that will be useful for the proof.
Let G = (A + B, E) be a bipartite graph with |A| = k and A = {a1 , ..., ak }. We call a
subset of edges M ⊆ E saturating if cov(M ) = B. Also, given some nonnegative integers
b1 , ..., bk , we say that M is a (b1 , ..., bk )-matching if |M ∩ δ(ai )| ≤ bi for each i ∈ [k].
Lemma 5. Consider the following multi-agent minimization problem
P
min
i∈[k] gi (Si )
s.t. S1 + · · · + Sk = V
Si ⊆ Vi
|Si | ≤ bi .
Then, if the functions gi are nonnegative monotone submodular there exists a polytime
(maxi bi )-factor approximation.
Proof. Apply the generic reduction from Section 2, and let G = ([k] + V, E) be the corresponding bipartite graph (i.e., with E = ⊎i∈[k] {(i, v) : v ∈ Vi }) and f the corresponding function. Define weights w : E → R+ such that we = f (e) for each e ∈ E. Let
M ⊆ E be any saturating (b1 , ..., bk )-matching in G. By submodularity of
Pf we have
that w(M ) ≥ f (M ). Moreover, since g can be written as g(S1 , ..., Sk ) =
i∈[k] gi (Si ),
P
we have that f (M ) =
f
(M
)
for
some
monotone
submodular
functions
fi where
i
i
i∈[k]
Mi := M ∩ δ(i) and fi (Mi ) = gi (cov(Mi )). Moreover, by monotonicity of the fi we have
fi (Mi ) ≥ max fi (e) = max f (e) ≥
e∈Mi

e∈Mi

1
1
1 X
w(Mi ) ≥ w(Mi )
f (e) =
|Mi |
|Mi |
bi
e∈Mi

where the first equality follows from the fact that f (e) = fi (e) for every e ∈ δ(i), and the
last inequality from the fact that M is a saturating (b1 , ..., bk )-matching and hence |Mi | ≤ bi
for every i ∈ [k]. Hence, it follows that for each saturating (b1 , ..., bk )-matching M we have
w(M ) ≥ f (M ) =

X

i∈[k]

fi (Mi ) ≥

X 1
X
1
1
(
w(Mi ) ≥
)w(Mi ) =
w(M ).
bi
maxi∈[k] bi
maxi∈[k] bi

i∈[k]

i∈[k]

In particular, if M ∗ is a minimum saturating (b1 , ..., bk )-matching for the weights w, we have
w(M ∗ ) ≥ f (M ∗ ) ≥ min
f (M )
≥
s.t. M is a saturating (b1 , ..., bk )-matching

1
∗
maxi∈[k] bi w(M ).

This is, f (M ∗ ) is a (maxi bi )-factor approximation. We conclude the argument by noticing
that w is a modular function, and hence we can find a minimum saturating (b1 , ..., bk )matching in polynomial time.
⊓
⊔
Corollary 11. Consider the above problem in the special case where k = n and all the
bi = 1. Then, an optimal solution to the problem is given by a minimum perfect matching
with respect to the weights w as defined in the proof above. Moreover, this solution is still
optimal even in the case where we do not require anymore the original functions gi to be
nonnegative or monotone.

28

Richard Santiago and F. Bruce Shepherd

Surprisingly, the above problem becomes very hard to approximate if we allow general
multivariate submodular functions instead of decomposable ones. This is true even under
the special conditions of Corollary 11 in which k = n and bi = 1 for all the agents.
Lemma 6. There is an information-theoretic hardness lower bound of Ω(n) for the multivariate problem
min g(S1 , . . . , Sk )
s.t. S1 + · · · + Sk = V
Si ⊆ Vi
|Si | ≤ 1
where g is a nonnegative monotone multivariate submodular function.
Proof. We prove this in the special case where k = n. Notice that in this case the constraint |Si | ≤ 1 becomes |Si | = 1. We reduce an instance of the submodular perfect matching (SPM) problem to the problem above. In [12], the following is shown for any fixed
1−3ǫ
ǫ, δ > 0. Any randomized ( n1+δ )-approximation algorithm for the submodular minimum
cost perfect matching problem on bipartite graphs (with at least one perfect matching),
requires exponentially many queries. So let us consider an instance of SPM consisting of
a bipartite graph G = (A + B, E) with |A| = |B| and a nonnegative monotone submodular function f : 2E → R+ . The goal is to find a perfect matching M ⊆ E of minimum submodular cost. We can transform this to the general multivariate problem above
by applying the reduction from Section 2 in the opposite direction. More formally, let
k = |A|, V = B, and Vi = cov(δ(ai )) where A = {a1 , ..., ak }. Also, define a multivariate function g : 2V1 × ... × 2Vk → R+ by g(S1 , ..., Sk ) = f (⊎i∈[k] {(ai , b) : b ∈ Si }) for
any (S1 , ..., Sk ) ∈ 2V1 × · · · × 2Vk (i.e. Si ⊆ Vi ). We have g is multivariate submodular by
Claim 2.2. It follows that a solution to
min g(S1 , . . . , Sk )
s.t. S1 + · · · + Sk = V
Si ⊆ Vi
|Si | = 1
(where here |V | = k) is a solution to the original SPM instance.

⊓
⊔

We conclude this section by showing that monotone MSCA (which admits an O(ln(n))approximation) becomes very hard when additional cardinality constraints are added.
Claim. The problem

Pk
min
i=1 fi (Si )
s.t. S1 + · · · + Sk = V
|Si | ≤ bi

√

where the fi are nonnegative monotone submodular functions is Ω( ln nn )-hard. This is even
the case when k = 2.
Proof. It is known ([41]) that the problem
min f (S) : |S| = m where f is a nonnegative
√
n
monotone submodular function is Ω( ln n )-hard. We reduce a general instance of this problem
to the problem of the claim. To see this notice that by monotonicity of f we have
min f (S) = min f (S) = min
f (S)
= min f (S) + f ′ (S ′ )
′
s.t. |S| = m s.t. |S| ≥ m s.t. S + S = V
s.t. S + S ′ = V
′
|S | ≤ |V | − m
|S ′ | ≤ |V | − m

where f ′ (S ′ ) = 0 for all S ′ ⊆ V .

⊓
⊔

Multi-Agent and Multivariate Submodular Optimization

29

References
1. Buchbinder, N., Feldman, M., Seffi, J., Schwartz, R.: A tight linear time (1/2)-approximation
for unconstrained submodular maximization. SIAM Journal on Computing 44(5), 1384–1402
(2015)
2. Calinescu, G., Chekuri, C., Pál, M., Vondrák, J.: Maximizing a monotone submodular function
subject to a matroid constraint. SIAM Journal on Computing 40(6), 1740–1766 (2011)
3. Chekuri, C., Ene, A.: Submodular cost allocation problem and applications. In: Automata,
Languages and Programming, pp. 354–366. Springer (2011)
4. Chen, C., Chester, S., Srinivasan, V., Wu, K., Thomo, A.: Group-aware weighted bipartite
b-matching. In: Proceedings of the 25th ACM International on Conference on Information and
Knowledge Management. pp. 459–468. ACM (2016)
5. Chen, C., Zheng, L., Srinivasan, V., Thomo, A., Wu, K., Sukow, A.: Conflict-aware weighted
bipartite b-matching and its application to e-commerce. IEEE Transactions on Knowledge and
Data Engineering 28(6), 1475–1488 (2016)
6. Conforti, M., Cornuéjols, G.: Submodular set functions, matroids and the greedy algorithm:
tight worst-case bounds and some generalizations of the rado-edmonds theorem. Discrete applied mathematics 7(3), 251–274 (1984)
7. Ene, A., Vondrák, J.: Hardness of submodular cost allocation: Lattice matching and a simplex
coloring conjecture. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) 28, 144–159 (2014)
8. Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by
tree metrics. In: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing. pp. 448–455. ACM (2003)
9. Feige, U., Mirrokni, V.S., Vondrak, J.: Maximizing non-monotone submodular functions. SIAM
Journal on Computing 40(4), 1133–1153 (2011)
10. Feldman, M., Naor, J., Schwartz, R.: A unified continuous greedy algorithm for submodular
maximization. In: Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on. pp. 570–579. IEEE (2011)
11. Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing
submodular set functions-II. Springer (1978)
12. Goel, G., Karande, C., Tripathi, P., Wang, L.: Approximability of combinatorial problems with
multi-agent submodular cost functions. In: Foundations of Computer Science, 2009. FOCS’09.
50th Annual IEEE Symposium on. pp. 755–764. IEEE (2009)
13. Goemans, M.X., Ramakrishnan, V.: Minimizing submodular functions over families of sets.
Combinatorica 15(4), 499–513 (1995)
14. Goemans, M.X., Soto, J.A.: Symmetric submodular function minimization under hereditary
family constraints. arXiv preprint arXiv:1007.2140 (2010)
15. Grötschel, M., Lovász, L., Schrijver, A.: Geometric algorithms and combinatorial optimization,
vol. 2. Springer Science & Business Media (2012)
16. Gupta, A., Roth, A., Schoenebeck, G., Talwar, K.: Constrained non-monotone submodular
maximization: Offline and secretary algorithms. In: International Workshop on Internet and
Network Economics. pp. 246–257. Springer (2010)
17. Hayrapetyan, A., Swamy, C., Tardos, É.: Network design for information networks. In: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. pp. 933–942.
Society for Industrial and Applied Mathematics (2005)
18. Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing submodular functions. Journal of the ACM (JACM) 48(4), 761–777 (2001)
19. Iwata, S., Nagano, K.: Submodular function minimization under covering constraints. In: Foundations of Computer Science, 2009. FOCS’09. 50th Annual IEEE Symposium on. pp. 671–680.
IEEE (2009)
20. Iwata, S., ichi Tanigawa, S., Yoshida, Y.: Bisubmodular function maximization and extensions.
Tech. rep., Technical Report METR 2013-16, The University of Tokyo (2013)

30

Richard Santiago and F. Bruce Shepherd

21. Khot, S., Lipton, R.J., Markakis, E., Mehta, A.: Inapproximability results for combinatorial
auctions with submodular utility functions. In: International Workshop on Internet and Network
Economics. pp. 92–101. Springer (2005)
22. Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2- ε. Journal of
Computer and System Sciences 74(3), 335–349 (2008)
23. Kolmogorov, V.: Submodularity on a tree: Unifying lˆ\ natural-convex and bisubmodular functions. In: Mathematical Foundations of Computer Science 2011, pp. 400–411. Springer (2011)
24. Krause, A., Guestrin, C.: Near-optimal observation selection using submodular functions. In:
AAAI. vol. 7, pp. 1650–1654 (2007)
25. Krause, A., Leskovec, J., Guestrin, C., VanBriesen, J., Faloutsos, C.: Efficient sensor placement optimization for securing large water distribution networks. Journal of Water Resources
Planning and Management 134(6), 516–526 (November 2008)
26. Krause, A., McMahan, H.B., Guestrin, C., Gupta, A.: Robust submodular observation selection.
Journal of Machine Learning Research 9(Dec), 2761–2801 (2008)
27. Krause, K., Goodwin, M., Smith, R.: Optimal software test planning through automated network analysis. TRW Systems Group (1973)
28. Kulik, A., Shachnai, H., Tamir, T.: Maximizing submodular set functions subject to multiple
linear constraints. In: Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete
Algorithms. pp. 545–554. Society for Industrial and Applied Mathematics (2009)
29. Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Non-monotone submodular maximization under matroid and knapsack constraints. In: Proceedings of the forty-first annual ACM
symposium on Theory of computing. pp. 323–332. ACM (2009)
30. Lee, J., Sviridenko, M., Vondrák, J.: Submodular maximization over multiple matroids via
generalized exchange properties. Mathematics of Operations Research 35(4), 795–806 (2010)
31. Lehmann, B., Lehmann, D., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. In: Proceedings of the 3rd ACM conference on Electronic Commerce. pp. 18–28. ACM
(2001)
32. Lehmann, B., Lehmann, D., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior 55(2), 270–296 (2006),
http://EconPapers.repec.org/RePEc:eee:gamebe:v:55:y:2006:i:2:p:270-296
33. Lovász, L.: Submodular functions and convexity. In: Mathematical Programming The State of
the Art, pp. 235–257. Springer (1983)
34. Mirrokni, V., Schapira, M., Vondrák, J.: Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In: Proceedings of the 9th ACM conference on
Electronic commerce. pp. 70–77. ACM (2008)
35. Mirzakhani, M.: personal communication with Alina Ene and Jan Vondrák (2014)
36. Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing
submodular set functions - i. Mathematical Programming 14(1), 265–294 (1978)
37. Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Mathematics of operations research 3(3), 177–188 (1978)
38. Orlin, J.B.: A faster strongly polynomial time algorithm for submodular function minimization.
Mathematical Programming 118(2), 237–251 (2009)
39. Orlin, J.B., Schulz, A.S., Udwani, R.: Robust monotone submodular function maximization.
In: International Conference on Integer Programming and Combinatorial Optimization. pp.
312–324. Springer (2016)
40. Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. Journal of Combinatorial Theory, Series B 80(2), 346–355 (2000)
41. Svitkina, Z., Fleischer, L.: Submodular approximation: Sampling-based algorithms and lower
bounds. SIAM Journal on Computing 40(6), 1715–1737 (2011)
42. Svitkina, Z., Tardos, É.: Facility location with hierarchical facility costs. ACM Transactions on
Algorithms (TALG) 6(2), 37 (2010)
43. Thapper, J., Zivny, S.: The power of linear programming for valued csps. In: Foundations of
Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on. pp. 669–678. IEEE (2012)

Multi-Agent and Multivariate Submodular Optimization

31

44. Vondrák, J.: Optimal approximation for the submodular welfare problem in the value oracle
model. In: Proceedings of the fortieth annual ACM symposium on Theory of computing. pp.
67–74. ACM (2008)
45. Vondrák, J.: Symmetry and approximability of submodular maximization problems. SIAM
Journal on Computing 42(1), 265–304 (2013)
46. Ward, J., Živnỳ, S.: Maximizing bisubmodular and k-submodular functions. In: Proceedings
of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 1468–1481.
SIAM (2014)

APPENDIX
A

Upwards-Closed (aka Blocking) Families

In this section, we give some background for blocking families. As our work for minimization
is restricted to monotone functions, we can often convert an arbitrary set family into its
upwards-closure (i.e., a blocking version of it) and work with it instead. We discuss this
reduction as well.
A.1

Blocking Families and a Natural Relaxation for P (F )

A set family F ′ , over a ground set V is upwards-closed if F ⊆ F ′ and F ∈ F ′ , implies that
F ′ ∈ F ′ ; these are sometimes referred to as blocking families. Examples of such families
include vertex-covers or set covers more generally, whereas spanning trees are not.
For a blocking family F ′ one normally works with the induced sub-family F of minimal
sets. Then F has the property that it is a clutter, that is, F does not contain a pair of
comparable sets, i.e., sets F ⊂ F ′ . If F is a clutter, then there is an associated blocking
clutter B(F ), which consists of the minimal sets B such that B ∩ F 6= ∅ for each F ∈ F .
We refer to B(F ) as the blocker of F . The same definition also yields B(F ′ ) = B(F ). The
following can be checked easily.
Claim (Lehman).
1. F ∈ F ′ if and only if F ∩ B 6= ∅ for all B ∈ B(F ).
2. B(B(F )) = F .
The significance of blockers is that one may assert membership in an upwards-closed family
F ′ by checking intersections on sets from the blocker B(F ). That is F ∈ F ′ if and only if
F ∩B 6= ∅ for each B ∈ B(F ). This simple observation gives a natural relaxation for exploring
minimization problems over the integral polyhedron P (F ′ ) = conv({χF : F ∈ F ′ }). The
blocking formulation for F ′ is:
P ∗ (F ′ ) = {z ∈ RV≥0 : z(B) ≥ 1 ∀B ∈ B(F )}.

(12)

Clearly we have P (F ′ ) ⊆ P ∗ (F ′ ).
A.2

Reducing to Blocking Families

Now consider an arbitrary set family F over V . We may define its upwards closure by
F ↑ = {F ′ : F ⊆ F ′ for some F ∈ F }. In this section we argue that in order to solve a

32

Richard Santiago and F. Bruce Shepherd

monotone optimization problem over sets in F it is often sufficient to work over its upwardsclosure.
As already noted B(F ) = B(F ↑ ) and hence one approach is via the blocking formulation
∗
P (F ) = P ∗ (F ↑ ). This requires two ingredients. First, we need a separation algorithm for
the blocking relaxation, but indeed this is often available for many natural families such as
spanning trees, perfect matchings, st-paths, and vertex covers. The second ingredient needed
′
is the ability to turn an integral solution χF from P ∗ (F ↑ ) or P (F ↑ ) into an integral solution
χF ∈ P (F ). We now argue that this is the case if a polytime separation algorithm is available
for the blocking relaxation P ∗ (F ↑ ) or for the polytope P (F ) := conv({χF : F ∈ F }).
For a polyhedron P , we denote its dominant by P ↑ := {z : z ≥ x for some x ∈ P }. The
following observation is straightforward.
Claim. Let H be the set of vertices of the hypercube in RV . Then
H ∩ P (F ↑ ) = H ∩ P (F )↑ = H ∩ P ∗ (F ↑ ).
In particular we have that χS ∈ P (F )↑ ⇐⇒ χS ∈ P ∗ (F ↑ ).
We can now use this observation to prove the following.
Lemma 7. Assume we have a separation algorithm for P ∗ (F ↑ ). Then for any χS ∈ P ∗ (F ↑ )
we can find in polytime χM ∈ P (F ) such that χM ≤ χS .
Proof. Let S = {1, 2, . . . , k}. We run the following routine until no more elements can be
removed:
For i ∈ S
If χS−i ∈ P ∗ (F ↑ ) then S = S − i
Let χM be the output. We show that χM ∈ P (F ). Since χM ∈ P ∗ (F ↑ ), by Claim A.2
we know that χM ∈ P (F )↑ . Then by definition of dominant there exists x ∈PP (F ) such
that x ≤ χM ∈ P (F )↑ . It followsP
that the vector x can be written as x = i λi χUi for
some Ui ∈ F and λi ∈ (0, 1] with i λi = 1. Clearly we must have that Ui ⊆ M for all i,
otherwise x would have a non-zero component outside M . In addition, if for some i we have
Ui ( M , then there must exist some j ∈ M such that Ui ⊆ M − j ( M . Hence M − j ∈ F ↑ ,
and thus χM−j ∈ P (F )↑ and χM−j ∈ P ∗ (F ↑ ). But then when component j was considered
in the algorithm above, we would have had S such that M ⊆ S and so χS−j ∈ P ∗ (F ↑ ) (that
is χS−j ∈ P (F )↑ ), and so j should have been removed from S, contradiction.
⊓
⊔
We point out that for many natural set families F we can work with the relaxation
P ∗ (F ↑ ) assuming that it admits a separation algorithm. Then, if we have an algorithm
′
which produces χF ∈ P ∗ (F ↑ ) satisfying some approximation guarantee for a monotone
problem, we can use Lemma 7 to construct in polytime F ∈ F which obeys the same
guarantee.
Moreover, notice that for Lemma 7 to work we do not need an actual separation oracle
for P ∗ (F ↑ ), but rather all we need is to be able to separate over 0 − 1 vectors only. Hence,
since the polyhedra P ∗ (F ↑ ), P (F ↑ ) and P (F )↑ have the same 0 − 1 vectors (see Claim A.2),
a separation oracle for either P (F ↑ ) or P (F )↑ would be enough for the routine of Lemma
7 to work. We now show that this is the case if we have a polytime separation oracle for
P (F ). The following result shows that if we can separate efficiently over P (F ) then we can
also separate effficiently over the dominant P (F )↑ .

Multi-Agent and Multivariate Submodular Optimization

33

Claim. If we can separate over a polyhedron P in polytime, then we can also separate over
its dominant P ↑ in polytime.
Proof. Given a vector y, we can decide whether y ∈ P ↑ by solving
x+s=y
x∈P
s ≥ 0.
Since can we easily separate over the first and third constraints, and a separation oracle for
P is given (i.e. we can also separate over the set of constraints imposed by the second line),
it follows that we can separate over the above set of constraints in polytime.
⊓
⊔
Now we can apply the same mechanism from Lemma 7 to turn feasible sets from F ↑ into
feasible sets in F .
Corollary 12. Assume we have a separation algorithm for P (F )↑ . Then for any χS ∈
P (F )↑ we can find in polytime χM ∈ P (F ) such that χM ≤ χS .
We conclude this section by making the remark that if we have an algorithm which
′
produces χF ∈ P (F ↑ ) satisfying some approximation guarantee for a monotone problem,
we can use Corollary 12 to construct F ∈ F which obeys the same guarantee.

B

Relaxations for Constrained Submodular Minimization

Submodular optimization techniques for minimization on a set family have involved two
standard relaxations, one being linear [12] and one being convex [19,3]. We introduce these
in this section.
B.1

A Convex Relaxation

We will be working with upwards-closed set families F , and their blocking relaxations P ∗ (F ).
As we now work with arbitrary vectors z ∈ [0, 1]n , we must specify how our objective function
f (S) behaves on all points z ∈ P ∗ (F ). Formally, we call g : [0, 1]V → R an extension of f if
g(χS ) = f (S) for each S ⊆ V . Conversely, if g : [0, 1]V → R is a function, then we call its
set restriction the function f (S) = g(χS ) for each S ⊆ V .
If our relaxation is to be algorithmically useful, one anticipates the extension g to be
convex. For a submodular objective function f (S) there can be many convex extensions
of f to [0, 1]V (or to RV ). The most popular one has been the so-called Lovász Extension
(introduced in [33]) due to several of its desirable properties.
We give one of several equivalent definitions for the Lovász Extension. Let 0 < v1 < v2 <
... < vm ≤ 1 be the distinct positive values taken in some vector z ∈ [0, 1]V . We also define
v0 = 0 and vm+1 = 1 (which may be equal to vm ). Define for each i ∈ {0, 1, ..., m} the set
Si = {j : zj > vi }. In particular, S0 is the support of z and Sm = ∅. One then defines:
f L (z) =

m
X
i=0

(vi+1 − vi )f (Si ).

Lemma 8 (Lovász [33]). The function f L is convex if and only if f is submodular.

34

Richard Santiago and F. Bruce Shepherd

One could now attack constrained submodular minimization by solving the problem
min f L (z) : z ∈ P ∗ (F ) and then seek rounding methods for the resulting solution. This is
the approach used in [19,3].
We will later use two additional properties of the Lovász Extension. We say that a
function g is (positively) homogeneous if for each c ≥ 0, we have g(cz) = cg(z).
Lemma 9. The Lovász Extension of f is homogeneous if f is submodular and normalized
(i.e. f (∅) = 0). That is for any x ∈ [0, 1]n and α ∈ [0, 1] f L (αx) = αf L (x). In particular,
for any set Q we have f L ((α)χQ ) = αf (Q).
Proof. This follows by construction. Recall that
f L (x) =

m
X
i=0

(vi+1 − vi )f (Si )

where v0 = 0, vm+1 = 1, and 0 ≤ v1 < v2 < ... < vm ≤ 1 are the distinct values taken in
the vector x ∈ [0, 1]n . The sets Si are defined as Si = {j : xj > vi } for each i ∈ {0, 1, ..., m}.
It follows directly that
L

f (αx) =

m−1
X
i=0

(α)(vi+1 − vi )f (Si ) + (1 − αvm )f (∅) = αf L (x)

Lemma 10. If f (S) is a monotonic set function, then f L is a monotonic function.

⊓
⊔

This can be used to establish the following.
V
Corollary
function. Suppose
Pa convex, monotonic, homogeneous
P13. Let Sg : [0, 1] → R be
if f L is the extension of
that z ≤ S x(S)χ , then g(z) ≤ S x(S)g(χS ). In particular,P
a normalized, monotonic, submodular function f (S) and χZ ≤ S x(S)χS , then f (Z) ≤
P
S x(S)f (S).

Proof.PWe prove the latter statement, the first being similar. Without loss of generality,
C := S⊆V x(S) > 0. Hence:
f (Q) = f L (χQ )
(by definition)
L
Q
= C
f
(χ
)
C
Q
= Cf L ( C1 χP
)
(by homogeneity)
L 1
≤ Cf ( C S⊆V x(S)χS ) (by monotonicity)
P
L
S
≤ C S⊆V ( x(S)
(by convexity)
C )f (χ )
P
L
S
= S⊆V x(S)f (χ )
P
(by definition).
= S⊆V x(S)f (S).
⊓
⊔
B.2

An Extended LP Formulation

By Claim A.1 (see Appendix A), an integer programming formulation for the single-agent
problem is
P
f (S)x(S)
min
P
P S⊆V
(13)
x(S)
≥ 1, ∀B ∈ B(F )
s.t.
v∈B
S∋v
x(S) ≥ 0.

Multi-Agent and Multivariate Submodular Optimization

35

The corresponding dual is given by
P
max
B∈B(F ) yB
P
P
s.t.
v∈S
B∋v yB ≤ f (S), ∀S ⊆ V
yB ≥ 0.

(14)

Using the ideas from [12], one may solve these LPs in polytime if the blocking family is
not too large.
Lemma 11. If f is submodular and |B(F )| ∈ poly(n), then the linear programs (13,14) can
be solved in polytime.
Proof. It is well-known [15] that a class of LPs can be solved in polytime if (i) it admits
a polytime separation algorithm and (ii) has a polynomially bounded number of variables.
Moreover, if this holds, then the class of dual problems can also be solved in polytime.
Hence we focus on the dual (14) for which condition (ii) is assured by our assumption
on |B(F )|.
PLet’sPnow consider its separation problem. For a fixed vector y ≥ 0 we define
zy (S) := v∈S v∈B yB for any S ⊆ V . Notice that zy is a modular function. Hence, f − zy
is submodular and so we can solve the problem minS⊆V f (S) − zy (S) exactly in polytime. It
follows that y is feasible if and only if this minimum is nonnegative. Thus, we can separate
in the dual efficiently.
⊓
⊔
The restriction that |B(F )| ∈ poly(n) is quite severe and we now show how it may be
weakened.
B.3

A Combined LP and Convex Program

In this section we show that one may solve the extended LP approximately as long as a
polytime separation algorithm for P ∗ (F ) is available. To do this, we work with a combination
of the LP and the convex relaxation from the prior section. For a feasible solution x to (13),
we define its image as
X
z=
x(S)χS .
S

We sometimes work with an extended formulation
Q = {(x, z) : z is the image of feasible x for (13)}.
One establishes easily that P ∗ (F ) is just a projection of Q.
Lemma 12. P ∗ (F ) = {z : ∃x such that (x, z) ∈ Q}.
In fact, the convex and LP relaxations are equivalent in the following sense, due to the
pleasant properties of the Lovász Extension.
Lemma 13.
min{f L (z) : z ∈ P ∗ (F )} = min{f L (z) : (x, z) ∈ Q} = min{

X
S

x(S)f (S) : (x, z) ∈ Q}.

Moreover,
solution z ∗ ∈ P ∗ (F ) we may compute x∗ such that (x∗ , z ∗ ) ∈ Q
P ∗given a feasible
L ∗
and S x (S)f (S) = f (z ). This may be done in time polynomially bounded in n and the
encoding size of z ∗ .

36

Richard Santiago and F. Bruce Shepherd

Proof. The first equality follows from the preceding lemma.
PFor the second equality we
consider (x, z) ∈ Q. By Corollary 13, we have that f L (z) ≤ S x(S)f (S). Hence ≤ holds.
Conversely, suppose that z ∗ is an optimal solution for the convex optimization problem
and let x∗ be determined
sets” associated with z ∗ in the definition of f L . By
P ∗ by the “level
L ∗
definition we have S x (S)f (S) = f (z ). Moreover, one easily checks that since z ∗ (B) ≥ 1
for each blocking set B, we also have that x∗ is feasible for (13). Hence ≥ holds as well. ⊓
⊔
Polytime Algorithms. One may apply the Ellipsoid Method to obtain a polytime
algorithm which approximately minimizes a convex function over a polyhedron K as long
as various technical conditions hold. For instance, one could require that there are two
ellipsoids E(a, A) ⊆ K ⊆ E(a, B) whose encoding descriptions are polynomially bounded in
the input size for K. We should also have polytime (or oracle) access to the convex objective
function defined over Rn . In addition, one must be able to polytime solve the subgradient
problem for f .5 One may check that the subgradient problem is efficiently solvable for
Lovász extensions of polynomially encodable submodular functions. We call f polynomially
encodable if the values f (S) have encoding size bounded by a polynomial in n(we always
assume this for our functions). If these conditions hold, then methods from [15] imply that
for any ǫ > 0 we may find an approximately feasible solution for K which is approximately
optimal. By approximate here we mean for instance that the objective value is within ǫ of
the real optimum. This can be done in time polynomially bounded in n (size of input say)
and log 1ǫ . Let us give a few details for our application.
In our setting, the rightmost LP from the previous lemma is essentially identical to the
linear program (13); it just works over Q which is like carrying some extra meaningless
variables z. The preceding result says that we can work instead over the more compact (in
terms of variables) space P ∗ (F ) at the price of using a convex objective function. Our convex
problem’s feasible space is P ∗ (F ) and it is easy to verify that our optimal solutions will lie
in the 0 − 1 hypercube H. So we may define the feasible space to be H and the objective
function to be g(x) = f L (x) if x ∈ H ∩ P ∗ (F ) and = ∞ otherwise. (Clearly g is convex in
Rn since it is a pointwise maximum of two convex functions; alternatively, one may define
the Lovász Extension on Rn which is also fine.) Note that g can be evaluated in polytime
by the definition of f L as long as f is polynomially encodable. We can now easily find an
ellipsoid inside H and one containing H each of which has poly encoding size. We may thus
solve the convex problem to within ±ǫ-optimality in time bounded by a polynomial in n and
log 1ǫ . Note that our lemmas guarantee to produce (x∗ , z ∗ ) ∈ Q so we have exact feasibility.
One final comment about exact solvability of these problems. Since our convex problem is equivalent to an LP (over Q with nonzero coefficients on the x-variables), we know
that an optimal solution (x∗ , z ∗ ) will be determined at a vertex of the polyhedron Q. It is
straightforward to check by contradiction that z ∗ is in fact a vertex of P ∗ (F ). As any such
vertex is defined by an n × n nonsingular system, and hence by Cramer’s Rule, the encoding
size of z ∗ is polynomially bounded (in n). But then x∗ could also be viewed as a vertex to
a polyhedron of the form: {x : Ax = z ∗ , x ≥ 0}. The support of any such vertex is again
determined by a nonsingular linear system with at most n rows. As z ∗ is polybounded, so is
the encoding size of x∗ . Since f and x∗ are polynomially-encodable, we have the the optimal
solution to the rightmost LP (and hence all problems) is polynomially bounded. Hence we
can pre-select a polybounded ǫ > 0 which guarantees us to find the exact optimum, not just
an ǫ-optimal one. Thus we have the following.
5

For a given y, find a subgradient of f at y.

Multi-Agent and Multivariate Submodular Optimization

37

Corollary 14. Consider a class of problems F , f for which f ’s are submodular and polynomiallyencodable in n = |V |. If there is a polytime separation algorithm for the family of polyhedra
P ∗ (F ), then one may find an exact optimum z ∗ for the convex program in Lemma 13 in
polytime. By Lemma 13 we may also produce x∗ in polytime for which (x∗ , z ∗ ) ∈ Q and
P
∗
L ∗
S x (S)f (S) = f (z ).
B.4

The Multi-Agent Formulations

The formulations above have natural extensions to the multi-agent setting. In the following,
we only work with the extension of the LPs (13,14). This was already introduced in [12].
P
P
min
f (S)x(S, i)
S⊆V
P
P
P i∈[k] i
s.t. v∈B S∋v i∈[k] x(S, i) ≥ 1, ∀B ∈ B(F )
(15)
x(S, i) ≥ 0.
The dual is:
P
max
B∈B(F ) yB
P
P
s.t.
v∈S
B∋v yB ≤ fi (S), ∀i, S ⊆ V
yB ≥ 0.

(16)

Again, using the ideas from Goel et al. [12], one sees that separation over the dual
amounts to k submodular minimization problems (cf. Lemma 11). Hence if B(F ) is polybounded, we may solve the LP exactly.
We can also solve it in polytime, however, if we have polytime separation of P ∗ (F ). This
follows the approach from the previous section (see Lemma 13 and Corollary 14) except
our convex
Pprogram now has k vectors of variables z1 , z2 , . . . , zk (one for each agent) such
that z = i zi . We force the constraint z ∈ P ∗ (F ). We also havePconstraints forcing that
S
each zi is the image of an associated (xi (S)) vector, i.e. zi =
S x(S, i)χ . Then it is
∗
∗
∗
∗
) we can find in
straightforward to check that for any feasible z = z1 +
P· · · + zk ∈ PP(FP
polytime an x∗ that is feasible for (15) and such that i fiL (zi∗ ) = i S fi (S)x∗ (S, i).
These lead to the following two corollaries.
Corollary 15. Assume there is a polytime separation oracle for P ∗ (F ). Then we can solve
the multi-agent LP described by (15) in polytime.
Corollary 16. Assume we can solve the single-agent LP described by (13) in polytime.
Then we can also solve the multi-agent LP described by (15) in polytime.
Proof. If we can solve (13) then we can also solve the convex program from Lemma 13.
Hence, we can separate over P ∗ (F ) in polynomial time. Now the statement follows from
Corollary 15.
⊓
⊔

C

Properties of multivariate submodular functions

In this section we discuss several properties of multivariate submodular functions. We see
that some of the characterizations and results that hold for univariate submodular functions
extend naturally to the multivariate setting.
We start by showing that our definition of submodularity in the multivariate setting
captures the diminishing return property. Recall that we usually think of the pair (i, v) ∈
[k] × V as the assignment of element v to agent i. We use this to introduce some notation
for adding an element to a tuple.

38

Richard Santiago and F. Bruce Shepherd

Definition 1. Given a tuple (S1 , . . . , Sk ) ∈ (2V )k and (i, v) ∈ [k] × V , we denote by
(S1 , . . . , Sk ) + (i, v) the new tuple (S1 , . . . , Si−1 , Si + v, Si+1 , . . . , Sk ).
Then, it is natural to think of the quantity
f (S1 , . . . , Si−1 , Si + v, Si+1 , . . . , Sk ) − f (S1 , . . . , Si−1 , Si , Si+1 , . . . , Sk )

(17)

as the marginal gain of assigning element v to agent i in the tuple (S1 , . . . , Sk ). Notice that
with the notation introduced in Definition 1 we have that (17) can be also written as
f ((S1 , . . . , Sk ) + (i, v)) − f (S1 , . . . , Sk ).
This leads to the following diminishing returns characterizations in the multivariate setting.
Proposition 3. A multivariate function f : (2V )k → R is multi-submodular if and only if
for all tuples (S1 , . . . , Sk ) ⊆ (T1 , . . . , Tk ) and (i, v) ∈ [k] × V we have
f ((S1 , . . . , Sk ) + (i, v)) − f (S1 , . . . , Sk ) ≥ f ((T1 , . . . , Tk ) + (i, v)) − f (T1 , . . . , Tk ).

(18)

Proof. We make use of the lifting reduction presented in Section 2.1. Let π : (2V )k → 2E
denote the bijection discussed in Section 2.1, and let f ′ : 2E → R be the univariate function
defined by f ′ (S) = f (π −1 (S)). Also, let S := π(S1 , . . . , Sk ) and T := π(T1 , . . . , Tk ). Since
(S1 , . . . , Sk ) ⊆ (T1 , . . . , Tk ) we know that S ⊆ T . Moreover, notice that
f ((S1 , . . . , Sk ) + (i, v)) − f (S1 , . . . , Sk ) = f ′ (S + (i, v)) − f ′ (S)
and
f ((T1 , . . . , Tk ) + (i, v)) − f (T1 , . . . , Tk ) = f ′ (T + (i, v)) − f ′ (T ).
In addition, from Claim 2.2 in Section 2.2 we know that f is multi-submodular if and only
if f ′ is submodular. Then the result follows by observing the following.
f multi-submodular
⇐⇒ f ′ submodular
⇐⇒ f ′ (S + (i, v)) − f ′ (S) ≥ f ′ (T + (i, v)) − f ′ (T )

for all S ⊆ T and (i, v) ∈ E

⇐⇒ f ((S1 , . . . , Sk ) + (i, v)) − f (S1 , . . . , Sk ) ≥ f ((T1 , . . . , Tk ) + (i, v)) − f (T1 , . . . , Tk )
for all (S1 , . . . , Sk ) ⊆ (T1 , . . . , Tk ) and (i, v) ∈ [k] × V.
⊓
⊔

The proof from the above proposition also shows the following characterization for multivariate submodular functions.
Proposition 4. A multivariate function f : (2V )k → R is multi-submodular if and only if
for all tuples (S1 , . . . , Sk ) and (i, v), (j, u) ∈ [k] × V we have
f ((S1 , . . . , Sk )+(i, v))−f (S1 , . . . , Sk ) ≥ f ((S1 , . . . , Sk )+(j, u)+(i, v))−f ((S1 , . . . , Sk )+(j, u)).
(19)
We now provide an explicit example of a multi-submodular function that leads to interesting applications.

Multi-Agent and Multivariate Submodular Optimization

39

Lemma 14. Consider a quadratic function h : Zk+ → R given by h(z) = z T Az for some matrix A = (aij ). Let f : (2V )k → R be a multivariate set function defined as f (S1 , . . . , Sk ) =
h(|S1 |, . . . , |Sk |). Then, f is multi-submodular if and only if A satisfies
aij + aji ≤ 0

∀i, j ∈ [k].

(20)

Proof. By Proposition 4 we know that f is multi-submodular if and only if condition (19)
is satisfied. Let (S1 , . . . , Sk ) be an arbitrary tuple and let (i, v), (j, u) ∈ [k] × V such that
v ∈
/ Si , u ∈
/ Sj . Denote by z 0 the integer vector with components zi0 = |Si |. That is,
0
z = (|S1 |, |S2 |, . . . , |Sk |) ∈ Zk+ . We call z 0 the cardinality vector associated to the tuple (S1 , . . . , Sk ). In a similar way, let z 1 be the cardinality vector associated to the tuple
(S1 , . . . , Sk ) + (i, v), z 2 the cardinality vector associated to (S1 , . . . , Sk ) + (j, u), and z 3 the
cardinality vector associated to (S1 , . . . , Sk ) + (i, v) + (j, u). Now notice that condition (19)
can be written as
h(z 1 ) − h(z 0 ) ≥ h(z 3 ) − h(z 2 )
(21)

for all z 0 , z 1 , z 2 , z 3 ∈ Zk+ such that z 1 = z 0 + ei , z 2 = z 0 + ej , and z 3 = z 0 + ei + ej , where
ei is the vector with all components equal to zero except the ith component which equals
1, and similarly for ej .
We show that (21) is equivalent to (20). First notice that for a vector z = (z1 , . . . , zk )
Pk
the function h can be written as h(z) = l,m=1 alm zl zm . Then, using that zl1 = zl0 for all
l 6= i and zi1 = z10 + 1, we have
h(z 1 ) − h(z 0 ) =

k
X
l,m=1

1
alm zl1 zm
−

k
X

0
alm zl0 zm
=

k
X

ali zl0 +

0
aim zm
+ aii .

m=1

l=1

l,m=1

k
X

Similarly, using that zl3 = zl2 for all l 6= i and zi3 = zi2 + 1, we have
h(z 3 ) − h(z 2 ) =

k
X

ali zl2 +

l=1

k
X

2
aim zm
+ aii .

m=1

Thus, using that z 2 = z 0 + ej we get
h(z 1 ) − h(z 0 ) ≥ h(z 3 ) − h(z 2 )
⇐⇒
⇐⇒

k
X
l=1

k
X
l=1

ali zl0 +

k
X

m=1

0
aim zm
+ aii ≥

ali (zl0 − zl2 ) +

k
X
m=1

k
X

ali zl2 +

l=1

k
X

2
aim zm
+ aii

m=1

0
2
aim (zm
− zm
)≥0

⇐⇒ − aji − aij ≥ 0

⇐⇒ aji + aij ≤ 0.

⊓
⊔

