# Greedy algorithm for submodular optimzation

In these notes, https://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_3.pdf 4.2.1 exercise 1, the following argument works if $f$ takes values in the integers, but I don't know how to deal with it if $f$ can take values in the reals.

Problem: Given a monotone submodular function $f$ (whose value would be computed by an oracle) on N = {1, 2, . . . , m}, find the smallest set S ⊆ N such that f(S) = f(N).

A greedy algorithm for this problem is as follows:

1. $S \leftarrow\emptyset$
2. while $f(S) \neq f(N)$ {
3. ____find $i$ to maximize $f(S+i)-f(S)$
4. ____set $S \rightarrow S\cup \{i\}$
5. }
6. return $S$

Question: Show that this is a $1+\ln f(N)$ approximation algorithm.

An argument is as follows: If $O$ is an optimal set, we can show that for the $i$ chosen in line 3 of the algorithm,

$$f(S+i) - f(S) \geq \frac{f(N)-f(S)}{|O\setminus S|} \geq \frac{f(N)-f(S)}{|O|}$$

Now letting $S_k$ denote the set $S$ after the $k$'th iteration (so $S_0=\emptyset$), and $z_k = f(N)-f(S_k)$ i.e., $z_k$ the "amount left" after the k'th iteration (so $z_0=f(N)$), the above inequality implies

$$z_k \leq z_{k-1} - \frac{z_{k-1}}{|O|} = \left(1-\frac{1}{|O|}\right)z_{k-1}$$

And therefore $$z_k \leq \left(1-\frac{1}{|O|}\right)^{k}f(N) \leq f(N)\exp(-k/|O|).$$ Setting $k=|O|(1+\ln f(N))$, we have $z_k<1$, and because $f$ takes only integral values, it must be that $z_k=0$.

But the question does not stipulate $f$ take only integral values. How can you deal with an $f$ that takes non-negative reals?

• What happens if the link goes foul in the future? The question will stop making sense. So please copy the exercise into your question. Apr 30 '16 at 16:26
• You still haven't copied the question, only the background. Apr 30 '16 at 23:17

The claim isn't true in general. Given a monotone submodular function $f$ and a positive constant $C$, let $g = f/C$. The algorithm is oblivious to the change from $f$ to $g$, and on the other hand $1 + \ln g(N) = 1 + \ln f(N) - \ln C$. In particular, by choosing $C$ large enough, you can get that the approximation ratio is any small enough number (even smaller than one or smaller than zero!).
• So in fact, we could just say that if $f$ were allowed to take arbitrary non-negative reals then $\ln f(N)$ could be negative? Apr 30 '16 at 18:50
• So $f$ is perfectly fine to take reals if we impose a condition like $|f(S)-f(T)| \geq 1$ if $S$ and $T$ have non-empty symmetric difference. And it also means that for the integer case, you can get a tighter analysis if you divide $f$ by the HCF of the range of $f$. Apr 30 '16 at 21:01