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.