Suppose a set function $f(S)$ is submodular and non-increasing, meaning that for any $S'\subset S$, $f(S') \geq f(S)$. The problem is to minimize $f(S)$ s.t. $|S| \leq k$.

I am wondering if there are some references discussing approximation algorithms regarding this problem.

The reference I can find now discussed a similar problem: minimize a non-decreasing submodular function under (lower bound) cardinality constraint (i.e., $|S| \leq k$). But it is not obvious to me how to adapt the result to the previous problem.

Edit: the exact form of $f$ is known.

  • $\begingroup$ How is the function $f$ specified? If it is given as an oracle, then you need to look at all $k$-element subsets in the worst case: Assume that $f(S)=1$ if $|S|\le k-1$ and $f(S)=0$ for $|S|\ge k+1$, and assume that $f(S)=1$ for all $S$ with $|S|=k$ with a single exception $T$ with $f(T)=0$. How do you detect the subset $T$? $\endgroup$ – Gamow Sep 2 '18 at 4:07
  • $\begingroup$ For a set function $g$, let $f(S’) := g(S \setminus S’)$. Then $f$ is submodular nonincreasing iff $g$ is submodular nondecreasing, and a cardinality $k$ upper bound on $S’$ equals a cardinality $|S|-k$ lower bound on $S \setminus S’$, so I think the two problems are equivalent. $\endgroup$ – Yonatan N Sep 2 '18 at 9:07
  • $\begingroup$ If you add in the constraint that $f$ is nonnegative, this becomes (effectively) the problem discussed in the third to last paragraph of Sec 1.3 of Svitkina and Fleischer arxiv.org/pdf/0805.1071.pdf . Non-increasingness can be assumed w.l.o.g. $\endgroup$ – Yonatan N Sep 2 '18 at 9:32
  • $\begingroup$ @Gamow, the exact form of $f$ is known. $\endgroup$ – Paradox Sep 2 '18 at 15:32

If the only thing that you know about $f$ is that it is non-increasing, then there is a simple adversary argument to show that you need to examine the value of $f$ on at least ${n \choose k}$ inputs (e.g., all ${n \choose k}$ different sets of cardinality $k$) in the worst case. For instance, consider functions $f$ that are $+\infty$ on all sets of cardinality $<k$, and with arbitrary values on the sets of cardinality $k$, and $-\infty$ on all sets of cardinality $>k$. A similar argument shows that no useful approximation is possible, either.

So, to make the problem tractable, you need to restrict the class of allowable functions in some way.

  • $\begingroup$ I think the author meant to specify that $f$ is submodular. Though not in the body, (s)he says as much in the title. You can still pull off a similar construction. $\endgroup$ – Yonatan N Sep 2 '18 at 9:30
  • $\begingroup$ Sorry, I forgot the "submodular" condition in the body. $\endgroup$ – Paradox Sep 2 '18 at 15:29

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.