4
$\begingroup$

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.)

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ There is a strong lower bound for this problem even in the monotone case. See arxiv.org/abs/0805.1071 $\endgroup$
    – Chandra Chekuri
    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

0

Reset to default

Your Answer

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