Minimizing SubModular Function: Cardinality Given a submodular function f: 2^V to reals (not necessarily monotone), and an integer k, find a set S such that |S| &lt;= k and  such that f(S) is minimized.

When the size constraint is |S| >=k, the problem is NP-hard.  What is known about when the constraint is |S| &lt;= k?
It is NP-hard. Svitkina and Fleischer showed that there is no $o(\sqrt{n/\log n})$ approximation using only a polynomial number of queries.