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:


$S \leftarrow\emptyset$
while $f(S) \neq f(N)$ {
____find $i$ to maximize $f(S+i)-f(S)$
____set $S \rightarrow S\cup \{i\}$
}
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&lt;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?
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!).