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.
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 $&lt;k$, and with arbitrary values on the sets of cardinality $k$, and $-\infty$ on all sets of cardinality $&gt;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.