Submodular Functions

Let $E$ be a finite set. A function $f:\mathcal{P}(E)\to \mathbb{R}$ is called submodular if for all $S\subseteq T\subseteq E$, we have

$$F(T\cup \{\ell \})-f(T)\le f(S\cup \{\ell \})-f(S)$$

for all $\ell \in E\setminus T$. Equivalently, $f$ is submodular if for any $S,T\subseteq E$, we have

$$f(S)+f(T)\ge f(S\cup T)+f(S\cap T).$$

Since $\mathcal{P}(E)$ forms a poset, we can still define a submodular function as monotone if for every $T\subseteq S$, $f(T)\le f(S)$. One example of a monotone submodular function is the coverage function:

Examples of Submodular Functions

Linear (Modular) Functions:

Define a weight function $w:E\to \mathbb{R}$. Then the function

$$f(S)=\sum _{x\in S}w(x)$$

defines a linear modular function. If $w(x)\ge 0$ for all $x\in E$, then $f$ is also monotone.

Coverage Functions:

Let $\Omega =\{E_1,E_2,\dots ,E_n\}$ be a collection of subsets of some ground set. Then the function

$$f(S)=\left|\bigcup _{E_i\in S}{E}_i\right|\text{ for }S\subseteq \Omega$$

is called the coverage function.

Graph Cuts:

Let $V=\{v_1,\dots ,v_n\}$ be the vertices of a graph. For subset $S\subseteq V$, define the submodular function $f(S)$ to be the number of edges $e=(u,v)$ such that $u\in S$ and $v\in V-S$.

Optimization Problems

Maximizing under Cardinality Constraints

If the submodular function $f:\mathcal{P}(E)\to \mathbb{R}$ is monotone, then the poset nature ensures that the ground set $E$ gives an optimal solution. The problem becomes significantly more difficulty when adding a constraint on the cardinality:

$$\begin{array}{rlr}& \max & f(S)\\ & \text{s.t.}& |S|\le k\\ & & S\subseteq E\end{array}$$

However, there is a fairly straightforward greedy algorithm for this problem which provides a $(1-1/e)$-approximation:

Algorithm 7 Cornuejols et al. (1997)

procedure Greedy()

$S:=\emptyset$

while $|S|<k$ do

$e:=\arg\max_{e\in E}[f(S\cup\{e\})-f(S)]$

$S:=S\cup\{e\}$

end while

end procedure

Unless $P=NP$, for any $ϵ>0$, there is no $(1-1/e+ϵ)$-approximation algorithm.

Maximizing under Matroid Constraints

A matroid $\mathcal{I}$ is a collection of subsets of a ground set $E$, called independent sets, such that

• $\varnothing \in \mathcal{I}$;
• if $S\in \mathcal{I}$, then $S^{\prime }\subseteq S\Rightarrow S^{\prime }\in \mathcal{I}$;
• if $S,T\in \mathcal{I}$ and $|S|<|T|$, then there is some $x\in T\setminus S$ such that $S\cup \{x\}\in \mathcal{I}$. For instance, the set $\{S\subseteq E:|S|\le k\}$ is the uniform matroid of rank $k$.

Every finite graph $G$ gives rise to a matroid $M(G)$ as follows:

• Let $E$ be the set of all edges in $G$.
• For $E^{\prime }\subseteq E$, define $E^{\prime }\in M(G)$ if and only if it is a forest, i.e., it does not contain a cycle. The resulting matroid is called the cycle matroid. Any matroid derived from a graph in this fashion is called graphic.

A base of a matroid $\mathcal{I}$, is an independent set $S\in \mathcal{I}$ such that $\nexists S^{\prime }\supseteq S$ such that $S^{\prime }\in \mathcal{I}$.

Given a matroid $\mathcal{I}$, one may define a polytope

$$\mathcal{P}=\{x\in {\mathbb{R}}_{+}^n\mid \sum _{i\in S}{x}_i\le r(S),\forall S\subseteq E\}$$

where $r:\mathcal{P}(E)\to \mathbb{R}$ is the submodular rank function defined by

$$r(S)=\max \{|S^{\prime }|:S^{\prime }\subseteq S,S^{\prime }\in \mathcal{I}\}.$$

The extreme points of $\mathcal{P}$ correspond to independent sets of $\mathcal{I}$. Consider maximizing a monotone submodular function under matroid constraints:

$$\begin{array}{rlr}& \max & f(S)\\ & \text{s.t.}& S\in \mathcal{I}\\ & & S\subseteq E\end{array}$$

The following greedy algorithm uses our polytope and gives a $(1/2-ϵ)$-approximation. Define multilinear function $F:[0,1{]}^n\to \mathbb{R}$ by

$$F(x)=\sum _{S\in E}f(S)\prod _{i\in S}{x}_i\prod _{i\notin S}(1-x_i)$$

which extends our submodular function $f$ into a continuous form.

Algorithm 8 Nemhauser et al. (1978)

procedure ContinuousGreedy()

$y:=0\in\R^n$

for all $t\in[0,1]$ do

$w_i:=F(\max\{y(t),e_i\})-F(y(t))$ for each $i\in E$

$x(t):=\arg\max_{x\in\mathcal{P}}\langle w(t),x\rangle$

Increase $y(t)$ at rate $dy(t)/dt=x(t)$

end for

return $y(1)=\int_0^1x(t)dt$

end procedure

Simply checking the extreme points of $\mathcal{P}$ provides a $(1-1/e)$-approximation.

Additional Resources

• Submodular Function Maximization, Andreas Krause, Daniel Golovin
• EE563 - Submodular Functions, Optimization, and Applications to Machine Learning, Jeff Bilmes
• High-performance Submodular Function Minimization (HPSFO), Giovanni Azua