# Reference request — minimizing a non-increasing submodular function with (upper bound) cardinality constraint

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.

• 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$? – Gamow Sep 2 '18 at 4:07
• 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. – Yonatan N Sep 2 '18 at 9:07
• 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. – Yonatan N Sep 2 '18 at 9:32
• @Gamow, the exact form of $f$ is known. – Paradox Sep 2 '18 at 15:32
• @YonatanN, thanks, I will check that. – 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.
• 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. – Yonatan N Sep 2 '18 at 9:30