I would like to know what the status of the following question is:

Given query access to a non-decreasing, non-negative submodular function $f\colon 2^{[n]} \to \mathbb{R}$ and a parameter $0 \leq m\leq n$, minimize $f(x)$ subject to the cardinality constraint $\lvert x\rvert \geq m$.

I am in particular interested in the query complexity of the problem as a function of $n$ and $m$. Without the cardinality constraint, this can be done efficiently in strongly polynomial time (so a fortiori with polynomial query complexity); without the monotonicity, this becomes NP-Hard (I assume this gives little hope in terms of number of queries?).

But now, does the monotonicity buy us anything? And, if not, what about throwing the assumption that $m=n-o(n)$ — would that help?

I'm at a loss about where to look — any answer, pointer, or reference would be welcome.

Note: at the end of the day, what I am actually given is approximate query access to $f$ — i.e., blackbox access to a randomized algorithm that returns w.h.p. a good additive approximation of $f(x)$ for any point $x$. I'm not sure this fundamentally changes the problem, though, and in any case the exact version seems like a good place to start. (But if the approximate version had been considered in the literature, this would make my day.)

  • 2
    $\begingroup$ There is a strong lower bound for this problem even in the monotone case. See arxiv.org/abs/0805.1071 $\endgroup$ Jan 31, 2016 at 20:22
  • 2
    $\begingroup$ @ChandraChekuri comment --> answer? $\endgroup$
    – usul
    Feb 1, 2016 at 5:49
  • $\begingroup$ @ChandraChekuri Thanks! If you care about writing this as an answer, I'll accept it (otherwise, i can write one based on your comment and mark it as Community, if you prefer.) $\endgroup$
    – Clement C.
    Feb 1, 2016 at 20:33


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.