<p>I would like to know what the status of the following question is: </p>

<blockquote>
  <p>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$.</p>
</blockquote>

<p>I am in particular interested in the query complexity of the problem as a function of $n$ and $m$. Without the cardinality constraint, this <a href="https://en.wikipedia.org/wiki/Submodular_set_function#Submodular_Minimization" rel="nofollow">can be done efficiently in strongly polynomial time</a> (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?).</p>

<p>But now, does the monotonicity buy us anything? And, if not, what about throwing the assumption that $m=n-o(n)$ &mdash; would that help?</p>

<p>I'm at a loss about where to look &mdash; any answer, pointer, or reference would be welcome.</p>

<p><strong>Note:</strong> at the end of the day, what I am actually given is <em>approximate</em> query access to $f$ &mdash; 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.) </p>

CC BY-SA 3.0
2016-01-31T20:22:05.693Z
There is a strong lower bound for this problem even in the monotone case. See http://arxiv.org/abs/0805.1071
Chandra Chekuri
CC BY-SA 3.0
2016-02-01T05:49:20.327Z
@ChandraChekuri comment --> answer?
usul
CC BY-SA 3.0
2016-02-01T20:33:22.113Z
@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.)
Clement C.
<reference-request><submodularity><minimization>
Minimizing a monotone submodular function under a cardinality constraint
Clement C.
# Minimizing a monotone submodular function under a cardinality constraint

(Asked by: username_0 on 2016-01-31)

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](https://en.wikipedia.org/wiki/Submodular_set_function#Submodular_Minimization) (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.)

**Tags:** reference-request, submodularity, minimization

> **Comments:**
> **username_1**: There is a strong lower bound for this problem even in the monotone case. See http://arxiv.org/abs/0805.1071  
> **username_2**: @ChandraChekuri comment --> answer?  
> **username_0**: @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.)  

---

## 0 answers

