1
$\begingroup$

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?

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

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!).

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ Apr 30 '16 at 18:50
  • $\begingroup$ That's exactly right. $\endgroup$ Apr 30 '16 at 20:14
  • $\begingroup$ 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$. $\endgroup$ Apr 30 '16 at 21:01
  • $\begingroup$ Possibly. I'll let you check this out yourself. $\endgroup$ Apr 30 '16 at 21:02
  • $\begingroup$ See also Wolsey's generalization of greedy set cover (discussed e.g. here). $\endgroup$
    – Neal Young
    May 1 '16 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.