First, some context:

Submodular Functions

Submodular functions have the intuitive diminishing returns property. Formally, a submodular function $f:2^V \rightarrow \mathbb{R}$ assigns a subset $A \subseteq V$ a utility value $f(A)$ such that

$$f(A \cup \{i\}) - f(A) \geq f(B \cup \{i\}) - f(B)$$

for any $A \subseteq B \subseteq V$ and $i \in V \setminus B$. We call $V$ the ground set.

Note that this definition just means that adding an element $i$ to a subset $A$ of set $B$ yields at least much value (or more) as if we add $i$ to $B$. In other words, the marginal gain of adding $i$ to $A$ is greater or equal to the marginal gain of adding $i$ to $B$. The notation for the marginal gain is:

$$\Delta(i|A) = f(A \cup \{i\}) - f(A)$$

We can also define the marginal gain for a set, which is basically the same thing:

$$\Delta(B|A) = f(A \cup B) - f(A)$$

We say that a submodular function is monotone if for any $A \subseteq B \subseteq V$ we have $f(A) \leq f(B)$. Intuitively, this means that adding more elements to a set cannot decrease its value.

An example

Let $f(X) = max(X)$. We have the set $X= \{1,2,3,4,5\}$, and we choose $A = \{1,2\}$ and $B = \{1,2,5\}$.

Note that $f(A) = 2$ and $f(B)= 5$. The marginal gain of items $3,4$ is :

$$\Delta(3|A) = 1\\ \Delta(3|B)=0\\ \Delta(4|A) = 2 \\ \Delta(4|B) = 0$$

Note that $\Delta(i | A) \geq \Delta(i | B)$ for any choice of $i$, $A$ and $B$. This is because $f$ is submodular and monotone.

Maximization of monotone submodular functions

Since the functions we're dealing with are monotone, it is obvious that the set with maximum value is always the ground set $V$. However, we impose a cardinality constraint - that is, finding the set of size at most $k$ that maximizes the utility. Formally,

$$A^* = argmax_{A: |A| \leq k}f(A)$$

Unfortunately, this problem is NP-hard. Fortunately, a simple greedy algorithm provides a solution with a nice approximation guarantee, which we will prove soon. The algorithm starts with the empty set $A_0$, and then repeats the following step for $i = 0, ... , (k-1)$:

$$A_{i+1} = A_{i} \cup \left\{ argmax_{v \in V \setminus A_i} f(S_i \cup \{v\}) \right\}$$

Note that

$$\left\{ argmax_{v \in V \setminus A_i} f(S_i \cup \{v\}) \right\} = \left\{ argmax_{v \in V \setminus A_i} \Delta(v | A_i) \right\}$$

Greedy algorithm guarantee and proof

Let:

• $A_i = (v_1, v_2, ..., v_i)$ be the the chain formed by the greedy algorithm, as defined above
• $A^*= (v_1^*, v_2^*, ..., v_k^*)$ be the optimal solution, in an arbitrary order
• $f$ be a monotone submodular function. Let $f \geq 0$ (Update on 04/25/2019: I thought this was w.l.o.g., but Andrey Kolobov pointed out that we actually need $f$ to be non negative)
• $OPT = f(A^*)$, the value of the optimal solution.

We will prove that

$$f(A_k) \geq (1 - 1/e) OPT$$

Note that $1 - 1/e \approx 0.63$. We now proceed to the proof.

For all $i \le k$, we have:

$$\begin{align} f(A^*) &\leq f(A^* \cup A_i) &\text{Monotonicity} \\ &= f(A_i) + \sum_{j = 1}^k\Delta(v_j^* | A_i \cup \{v_1^*, v_2^*, ...,v_{j-1}^*\}) \\ &\leq f(A_i) + \sum_{z \in A^*}\Delta(z | A_i) & \text{Using submodularity} \\ &\leq f(A_i) + \sum_{z \in A^*}\Delta(v_{i+1}|A_i) & \text{$v_{i+1} = argmax_{v \in V \setminus A_i}\Delta(v|A_i)$} \\ &= f(A_i) + k \Delta(v_{i+1} | A_i) \end{align}$$

Rearranging the terms, we have proved that

$$\Delta(v_{i+1} | A_i) \geq \frac{1}{k}(OPT - f(A_i))$$

Now we define $\delta_i = OPT - f(A_i)$. This implies $\delta_i - \delta_{i+1} = f(A_{i+1}) -f(A_i) = \Delta(v_{i+1} \vert A_i)$

Plugging this into our previous equation, we have:

$$\delta_{i}- \delta_{i+1} \geq \frac{1}{k}(\delta_i)$$

In other words, we have proved that the element added at iteration $i+1$ by the greedy algorithm reduces the gap to the optimal solution by a significant amount - by at least $\dfrac{1}{k}(OPT - f(A_i))$. Another way to write the same equation is

$$\delta_{i+1} \leq (1 - \frac{1}{k})\delta_i$$

If we recursively apply this definition, we have that

$$\delta_k \leq \left({1 - \frac{1}{k}}\right)^k \delta_0$$

Now, $\delta_0 = OPT - f(\emptyset) \leq OPT$. Thus, using the well-known bound $1 - x \leq e^{-x}$ for $x \in \mathbb{R}$, we have that

$$\delta_k \leq \left({1 - \frac{1}{k}}\right)^k OPT \leq \frac{1}{e}OPT$$

We now plug the definition of $\delta_k$ back, to get

$$OPT - f(A_k) \leq \frac{1}{e} OPT$$

Or equivalently:

$$f(A_k) \geq \left(1 - \frac{1}{e}\right) OPT$$

Which concludes our proof.

Lazy greedy

The runtime of the greedy algorithm is $O(\vert V \vert k)$ function evaluations, since at each step we have to find the element from the ground set that maximizes the marginal gain. There is a trick we can do to make the running time faster in practice.

The trick involves using a max-heap ($O(1)$ lookup and $O(log(n))$ insertion) to keep an upper bound on the gain of each item. This upper bound comes straight from submodularity, and is as follows:

$$\Delta(v | A_{i}) \geq \Delta(v | A_{j}) \quad \forall j > i$$

Using this, at iteration $i+1$ we evaluate $\Delta(v \vert A_i)$ for the elements in the ground set in the max-heap order. As soon as $\Delta(v \vert A_i)$ is greater than the upper bound on the top of the heap, we do not need to evaluate any more elements - we select $v$. If we evaluate an element at the top of the heap and it does not satisfy this condition, we just insert it again with $\Delta(v \vert A_i)$ as the new upper bound.

While the worst case is the same, in practice this trick usually has enormous speedups over the standard greedy procedure.