P1: IML/SPH P2: IML/SPH QC: IML/SPH T1: IML

CB636-FM CB636-Lee CB636-Lee-v2.cls December 11, 2003 16:30 Char Count= 0

8
Optimizing Submodular Functions

Minimizing and maximizing submodular functions are fundamental unifying

problems in combinatorial optimization. In this chapter, some examples are
given, and we discuss aspects of the general problems of minimizing and max-
imizing submodular functions.

8.1 Minimizing Submodular Functions

Let M be a matroid. Recall the rank inequalities

xe ≤ rM (S), ∀ S ⊂ E(M)
e∈S

that, along with nonnegativity, describe PI(M) . The separation problem for the
rank inequalities is, for fixed x ∗ ∈ R E(M) , find S ⊂ E(M) so that

xe∗ > rM (S) .
e∈S

Define f : 2 E(M)
→ R by

f (S) := rM (S) − xe∗ .
e∈S

It is easy to check that f is submodular (by use of the fact that rM is). Moreover,
x ∗ violates a rank inequality if and only if the minimum of f (S), over S ⊂
E(M), is less than 0.
Thus an ability to minimize this particular submodular function efficiently,
provides a theoretically efficient algorithm, by use of the ellipsoid method, for
finding maximum-weight sets that are independent for a matroid or even for a
pair of matroids. Of course, we also know direct combinatorial algorithms for
these problems that are practically as well as theoretically efficient.

194

Cambridge Books Published

https://doi.org/10.1017/CBO9780511616655.011 Online ©online
Cambridge University
by Cambridge Press,
University Press 2010
P1: IML/SPH P2: IML/SPH QC: IML/SPH T1: IML
CB636-FM CB636-Lee CB636-Lee-v2.cls December 11, 2003 16:30 Char Count= 0

8.1 Minimizing Submodular Functions 195

Problem (Minimum-weight cuts and submodular minimization). Con-

sider a digraph G with distinguished vertices v, w ∈ V (G) with v = w, and
a “capacity” function c : E(G) → R+ . For S ⊂ V (G) \ {v, w}, define
 
f (S) := c(e) : e ∈ δG+ (S + v) .

[That is, f (S) is the sum of the capacities on the edges that point out of
S + v.] Prove that f is submodular, and describe how to determine the
minimum of f on V (G) \ {v, w}.

Problem (Maximum-cardinality matroid intersection and submodular

minimization). Let Mi be matroids on the common ground set E := E(Mi )
for i = 1, 2. Prove that f : 2 E → R defined by

f (S) := rM (S) + rM (E \ S)
1 2

is submodular, and explain how this relates to the problem of finding a

maximum-cardinality subset of E that is independent in both M1 and M2 .

Next, we discuss some aspects of the problem of minimizing a general

submodular function f : 2 E → R, where E is a finite set. First, we may as-
sume that f (∅) = 0 [by subtracting f (∅) from f if necessary]. We define
f : [0, 1] E → R in a certain way, so that f (x) := f (S(x)) for x ∈ {0, 1} E .

Every nonzero x ∈ [0, 1] E can be decomposed uniquely as x = mj=1 λ j x j ,
where

(i) m ≤ |E|;
(ii) λ j > 0, for j = 1, 2, . . . m;
(iii) x ∈ {0, 1} E , for j = 1, 2, . . . m;
j

(iv) x 1 ≥ x 2 ≥ · · · ≥ x m = 0.

m
Then we let f (x) := j=1 λ j f (S(x j )).

Theorem (Convexity of f and integer-valued minima). The function f is

convex and attains it minimum over [0, 1] E on {0, 1} E .

Cambridge Books Published

https://doi.org/10.1017/CBO9780511616655.011 Online ©online
Cambridge University
by Cambridge Press,
University Press 2010
P1: IML/SPH P2: IML/SPH QC: IML/SPH T1: IML
CB636-FM CB636-Lee CB636-Lee-v2.cls December 11, 2003 16:30 Char Count= 0

196 8 Optimizing Submodular Functions

Proof. First, we demonstrate that the function f is convex. Consider a point

x ∗ ∈ R+E and the linear program


fˆ(x ∗ ) := max xe∗ z e
e∈E

Subject to:

z e ≤ f (T ), ∀T ⊂E.
e∈T

The optimal objective-function value of a linear-programming maximization

problem is a convex function of the vector of objective-function coefficients.
Therefore, it suffices to prove that f = fˆ.
Without loss of generality, we can take E := {1, 2, . . . , n} and x1∗ ≥ x2∗
≥ · · · ≥ xn∗ . Let T j := {1, 2, . . . , j}, for j = 1, 2, . . . , n, and let T0 := ∅. The
proof of the characterization of PI(M) for a matroid M implies that


n / 0
fˆ(x ∗ ) = x ∗j f (T j ) − f (T j−1 )
j=1
n 
 
= x ∗j − x ∗j+1 f (T j )
j=1

(even though f need not be the rank function of a matroid), where we

∗
take xn+1 := 0. Letting λ j := x ∗j − x ∗j+1 , we get the decomposition x ∗ =
n ∗ ˆ ∗
j=1 λ j x(T j ) (we can ignore the j with λ j = 0); so we have f (x ) = f (x ).
E
Finally, we demonstrate that f is minimized at a vertex of [0, 1] . Let

x ∗ = mj=1 λ j x j ∈ [0, 1] E be a minimizer of f over [0, 1] E . If f (x ∗ ) = 0,
then f is also minimized by 0 ∈ {0, 1} E , because we have assumed that f (∅) =
f (0) = 0. Therefore, we may suppose that f (x ∗ ) < 0. If f (x j ) > f (x ∗ ) for
 
all j, then f (x ∗ ) = mj=1 λ j f (x j ) > mj=1 λ j f (x ∗ ). Because f (x ∗ ) < 0,
m 
we have 1 < j=1 λ j . However, x ∗ ∈ [0, 1] E implies that mj=1 λ j ≤ 1, so we
have a contradiction. Therefore, f (x j ) ≤ f (x ∗ ) for some j; hence, some x j
minimizes f .

There is a theoretically efficient algorithm for minimizing the convex function

f over [0, 1] E , by use of the ellipsoid method. In this way, we can find a
minimum of the submodular function f . Other, more combinatorial methods
generalize maximum-flow techniques.

Cambridge Books Published

https://doi.org/10.1017/CBO9780511616655.011 Online ©online
Cambridge University
by Cambridge Press,
University Press 2010
P1: IML/SPH P2: IML/SPH QC: IML/SPH T1: IML
CB636-FM CB636-Lee CB636-Lee-v2.cls December 11, 2003 16:30 Char Count= 0

8.2 Minimizing Submodular Functions Over Odd Sets 197

8.2 Minimizing Submodular Functions Over Odd Sets

In this section, we see how to use an efficient algorithm for minimizing a
submodular function as a subroutine in an efficient algorithm for minimizing
a submodular function f over subsets S of the ground set E intersecting a fixed
subset T of the ground set on an odd number of elements. First, some motivation
is given that is related to the maximum-weight matching problem.
Let H be a graph with weight function c on E(H ). We consider the maximum-
weight matching problem on H . We may as well assume that c is nonnegative,
as the set of matchings is an independence system and so no negative-weight
edge will appear in a maximum-weight matching. Next, we can make a copy
H of H , and join each i ∈ V (H ) to its copy i ∈ V (H ). Call this new graph G.
All edges of H and those extending between H and H are assigned 0 weight
as we extend c to the entire edge set of G.

weight function c 0 weights

H H'

Now, every matching S of H extends to a perfect matching of G having the same

weight – for each e ∈ S, take its copy e ∈ E(H ), and for each exposed vertex
i of H , take the edge joining i to its copy i ∈ H . Furthermore, every perfect
matching S of G induces a matching S ∩ E(H ) of H having the same weight.
Therefore, to efficiently find a maximum-weight matching of H , it suffices to
be able to find a maximum-weight perfect matching of G.
Therefore, let us assume now that we have an arbitrary graph G and
nonnegative-weight function c on E(G). Let M(G) be the set of perfect match-
ings of G. Considering the inequality characterization of the matching polytope
PM(G) (see the Matching Polytope Theorem, p. 109), it is easy to see that the
perfect-matching polytope PM(G) is the solution set of

(i) − xe ≤ 0, ∀ e ∈ E(G);

(ii) xe = 1, ∀ v ∈ V (G);
e∈δG (v)
 |W | − 1
(iii) xe ≤ , ∀ W ⊂ V (G) with |W | ≥ 3 odd.
e∈E(G[W ])
2

Cambridge Books Published

https://doi.org/10.1017/CBO9780511616655.011 Online ©online
Cambridge University
by Cambridge Press,
University Press 2010
P1: IML/SPH P2: IML/SPH QC: IML/SPH T1: IML
CB636-FM CB636-Lee CB636-Lee-v2.cls December 11, 2003 16:30 Char Count= 0

198 8 Optimizing Submodular Functions

Using equation (ii), it is easy to check that (iii) can be replaced with

(iii ) xe ≥ 1, ∀ W ⊂ V (G) with |W | odd;
e∈δG (W )

we simply note that

 |W | − 1   
2 xe ≤ − xe = 1 = − xe ≥ 1, .
e∈E(G[W ])
2 v∈W e∈δG (v) e∈δG (W )

Then, for x ∗ ∈ R E(G) satisfying (i), we can solve the separation problem for
(iii ) by minimizing the function

f (W ) := −1 + xe∗
e∈δG (W )

over odd cardinality subsets W of V (G). As we have seen (“Cuts” Problem,

p. 61), the function f is submodular.
Now, we turn back to the general problem of minimizing a submodular
function over subsets of the ground set intersecting a fixed subset on an odd
number of elements. To be precise, let f be a submodular function on E. Let
T be a subset of E. We describe an efficient method for solving

X ∗ := argmin { f (X ) : X ⊂ E, |X ∩ T | odd} .

We assume that we have, at our disposal, an efficient subroutine for ordinary

submodular-function minimization.

Step 1: Reduce the case of |T | odd to |T | even. We observe that an optimal X ∗

either contains all of T or it avoids some element of T . Therefore, we calculate

X T := argmin { f (X ) : X ⊂ E, T ⊂ X } ,

and, for all e ∈ T ,

X e := argmin { f (X ) : X ⊂ E − e, |X ∩ (T − e)| odd} .

The calculation of each X e is just like the calculation of X ∗ , but now we are
intersecting an even cardinality set on an odd number of elements. The calcu-
lation of X T is just an instance of ordinary submodular-function minimization,
but the effective ground set is just E \ T , as we can just “shrink” T to a single
element.

Cambridge Books Published

https://doi.org/10.1017/CBO9780511616655.011 Online ©online
Cambridge University
by Cambridge Press,
University Press 2010
P1: IML/SPH P2: IML/SPH QC: IML/SPH T1: IML
CB636-FM CB636-Lee CB636-Lee-v2.cls December 11, 2003 16:30 Char Count= 0

8.2 Minimizing Submodular Functions Over Odd Sets 199

Step 2: Solve a relaxation. Let U be a subset of E. We say that U splits T if

both T ∩ U and T \ U are nonempty. We wish to calculate

U := argmin { f (X ) : X ⊂ E, X splits T } .

Notice that, because T is even, the condition that X splits T is a weakening of

the condition that |X ∩ T | is odd. Therefore, if |U ∩ T | is odd, then we solve
our original problem by letting X ∗ = U .
Next, we specify how we can efficiently calculate U . For all distinct e, f ∈ T ,
we calculate

Ue, f := argmin { f (X ) : X ⊂ E − f, e ∈ X odd} .


The calculation of each of the |T2 | choices of Ue, f is just an ordinary
submodular-function minimization problem. Then we simply let
 
U = argmin f (Ue, f ) : e, f ∈ T .

Step 3: Recurse. At this point we can assume that |U ∩ T | (and hence, also
|T \ U |) is even, or we would have solved the problem in Step 2. Recursively,
we solve the following two subproblems:

U1 := argmin { f (X ) : X ⊂ E, |X ∩ (T ∩ U )|odd, X does not split T \ U } ;

U2 := argmin { f (X ) : X ⊂ E, |X ∩ (T \ U )| odd, X does not split T ∩ U } .

Although we still have some work left to do to justify this, the solution to our
main problem is just to set X ∗ to

argmin { f (U1 ), f (U2 )} .

We note that, for the calculations of U1 and U2 , we reduce the problems to

problems of the same type that we are attacking, by “shrinking” the set not
to be split to a single element. In doing so, the set that we need to intersect
on an odd cardinality set remains of even cardinality. Also, because |T | =
|T \ U | + |T ∩ U |, it is clear that the total number of recursive calls will be
less than T .

Theorem (Correctness for odd submodular minimization). If |U ∩ T | is

even, then X ∗ = argmin { f (U1 ), f (U2 )} solves

min { f (X ) : X ⊂ E, |X ∩ T | odd} .

Cambridge Books Published

https://doi.org/10.1017/CBO9780511616655.011 Online ©online
Cambridge University
by Cambridge Press,
University Press 2010
P1: IML/SPH P2: IML/SPH QC: IML/SPH T1: IML
CB636-FM CB636-Lee CB636-Lee-v2.cls December 11, 2003 16:30 Char Count= 0

200 8 Optimizing Submodular Functions

Proof. The proof is by contradiction. Suppose that X ∗ solves our main problem,
but f (X ∗ ) < f (U1 ) and f (X ∗ ) < f (U2 ). From the definition of U1 , we see that
X ∗ splits T \ U . Therefore, immediately, we have that X ∗ ∪ U splits T . Sym-
metrically, from the definition of U2 , we see that X ∗ splits T ∩ U . Therefore,
we have that X ∗ ∩ U splits T .
Now, because |T ∩ X ∗ | is odd and |T ∩ U | is even, exactly one of |T ∩
(X ∗ ∪ U )| and |T ∩ (X ∗ ∩ U )| is odd. We suppose that |T ∩ (X ∗ ∩ U )| is odd
(the other case, which is left for the reader, is handled symmetrically). By the
definition of X ∗ , we have
f (X ∗ ∩ U ) ≥ f (X ∗ ).
By the definition of U , we have
f (X ∗ ∪ U ) ≥ f (U ).
Then, by submodularity, we must have f (X ∗ ∩ U ) = f (X ∗ ) [and f (X ∗ ∪ U ) =
f (U )]. Now, (X ∗ ∩ U ) + (T ∩ U ) = (X ∗ ∩ U ) ∩ T . Therefore, |(X ∗ ∩ U ) +
(T ∩ U )| is odd and (X ∗ ∩ U ) + (T ∩ U ) does not split T \ U . Therefore, by the
definition of U1 , we have f (X ∗ ∩ U ) ≥ f (U1 ). However, because we have al-
ready established that f (X ∗ ∩ U ) = f (X ∗ ), we conclude that f (X ∗ ) ≥ f (U1 ),
which contradicts our assumption.

8.3 Maximizing Submodular Functions

For an interesting special case, we know an efficient algorithm for maximizing
a submodular function.

Problem (Maximum-cardinality matching and submodular maxi-

mization). Let G be an undirected graph and define f : 2 E(G) → R by
f (S) := |{v ∈ V (G) : e ∈ δG (v) for some e ∈ S}| − |S| ,
for S ⊂ E(G). Prove that f is submodular and that, if S maximizes f , then
f (S) is the maximum number of edges in a matching of G.

In general, maximizing a submodular function is hard. For example, the

difficult problem of determining whether a digraph has a directed Hamiltonian
tour is a problem of finding a maximum-cardinality set that is independent for
three matroids having a common ground set.

Problem (Maximum-cardinality p-matroid intersection and submodu-

lar maximization). Let Mi be matroids on the common ground set E :=

Cambridge Books Published

https://doi.org/10.1017/CBO9780511616655.011 Online ©online
Cambridge University
by Cambridge Press,
University Press 2010
P1: IML/SPH P2: IML/SPH QC: IML/SPH T1: IML
CB636-FM CB636-Lee CB636-Lee-v2.cls December 11, 2003 16:30 Char Count= 0

8.4 Further Study 201

E(Mi ), for i = 1, 2, . . . , p. Define a submodular function f : 2 E → R by


p
f (S) := rM ∗ (S) .
i
i=1

Prove that the problem of finding a maximum-weight set that is independent

in all p matroids can be recast as a problem of finding a set S that maximizes
f (S).

Hard submodular maximization problems arise in other domains as well.

Problem (Uncapacitated facility location and submodular maximiza-

tion). Recall the “Uncapacitated facility location” Problem (see p. 6).
Demonstrate how the uncapacitated facility-location problem can be mod-
eled as a problem of maximizing a submodular function.

Another favorite hard problem can also be modeled as a problem of maxi-

mizing a submodular function.

Problem (Vertex packing and submodular maximization).

a. Recall the entropy function H (see p. 191). Prove that H is a submodular
function.
b. Let G be a simple graph. Let C be the symmetric matrix, with row and
columns indexed by V (G), having
⎧
⎨ 1, if {i, j} ∈ E(G)
ci j := 0, if i = j and {i, j} ∈
/ E(G).
⎩
3|V (G)|, if i = j

The matrix C is symmetric and positive definite. Notice that if E(G[S]) =

∅, then H (S) = |S| · ln(3|V (G)|). Prove that if E(G[S]) = ∅, then
H (S) < |S| · ln(3|V (G)|).

8.4 Further Study

The first theoretically efficient algorithm for minimizing a submodular func-
tion was based on the ellipsoid method; see Grötschel, Lovász and Schrijver
(1988). The first theoretically efficient combinatorial algorithms are due (simul-
taneously!) to Iwata, Fleischer, and Fujishige (1999) and to Schrijver (2000).

Cambridge Books Published

https://doi.org/10.1017/CBO9780511616655.011 Online ©online
Cambridge University
by Cambridge Press,
University Press 2010
P1: IML/SPH P2: IML/SPH QC: IML/SPH T1: IML
CB636-FM CB636-Lee CB636-Lee-v2.cls December 11, 2003 16:30 Char Count= 0

202 8 Optimizing Submodular Functions

None of these algorithms should be regarded as practical. However, their exis-

tence, together with the known practical and theoretically efficient algorithms
for the minimization of particular submodular functions, suggests that it is use-
ful to know whether a particular combinatorial-optimization problem can be
regarded as a problem of minimizing a submodular function.
The work by McCormick (2003) is a very nice survey of the state-of-the-art
algorithms for minimizing submodular functions.

“It is true what Madame says,” observed Jacques Three. “Why stop?
There is great force in that. Why stop?”
“Well, well,” reasoned Defarge, “but one must stop somewhere.
After all, the question is still where?”
– A Tale of Two Cities (C. Dickens)

Cambridge Books Published

https://doi.org/10.1017/CBO9780511616655.011 Online ©online
Cambridge University
by Cambridge Press,
University Press 2010