Reference request --- minimizing a non-increasing submodular function with (upper bound) cardinality constraint
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.