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

<p>So, to make the problem tractable, you need to restrict the class of allowable functions in some way.</p>

CC BY-SA 4.0
2018-09-02T09:30:47.633Z
I think the author meant to specify that $f$ is submodular. Though not in the body, (s)he says as much in the title. You can still pull off a similar construction.
Yonatan N
CC BY-SA 4.0
2018-09-02T15:29:05.967Z
Sorry, I forgot the "submodular" condition in the body.
Paradox
CC BY-SA 4.0
2018-09-01T23:40:39.523Z
2018-09-01T23:40:39.523Z
D.W.
<p>Suppose a set function $f(S)$ is submodular and non-increasing, meaning that for any $S'\subset S$, $f(S') \geq f(S)$. The problem is to minimize $f(S)$ s.t. $|S| \leq k$.</p>

<p>I am wondering if there are some references discussing approximation algorithms regarding this problem.</p>

<p>The reference I can find now discussed a similar problem: minimize a non-decreasing submodular function under (lower bound) cardinality constraint (i.e., $|S| \leq k$). But it is not obvious to me how to adapt the result to the previous problem.</p>

<p>Edit: the exact form of $f$ is known. </p>

CC BY-SA 4.0
2018-09-02T04:07:42.543Z
How is the function $f$ specified? If it is given as an oracle, then you need to look at all $k$-element subsets in the worst case: Assume that $f(S)=1$ if $|S|\le k-1$ and $f(S)=0$ for $|S|\ge k+1$, and assume that $f(S)=1$ for all $S$ with $|S|=k$ with a single exception $T$ with $f(T)=0$. How do you detect the subset $T$?
Gamow
CC BY-SA 4.0
2018-09-02T09:07:22.847Z
For a set function $g$, let $f(S’) := g(S \setminus S’)$. Then $f$ is submodular nonincreasing iff $g$ is submodular nondecreasing, and a cardinality $k$ upper bound on $S’$ equals a cardinality $|S|-k$ lower bound on $S \setminus S’$, so I think the two problems are equivalent.
Yonatan N
CC BY-SA 4.0
2018-09-02T09:32:44.413Z
If you add in the constraint that $f$ is nonnegative, this becomes (effectively) the problem discussed in the third to last paragraph of Sec 1.3 of Svitkina and Fleischer https://arxiv.org/pdf/0805.1071.pdf . Non-increasingness can be assumed w.l.o.g.
Yonatan N
CC BY-SA 4.0
2018-09-02T15:32:24.533Z
@Gamow, the exact form of $f$ is known.
Paradox
<optimization><submodularity>
Reference request --- minimizing a non-increasing submodular function with (upper bound) cardinality constraint
Paradox
# Reference request --- minimizing a non-increasing submodular function with (upper bound) cardinality constraint

(Asked by: username_0 on 2018-09-01)

Suppose a set function $f(S)$ is submodular and non-increasing, meaning that for any $S'\subset S$, $f(S') \geq f(S)$. The problem is to minimize $f(S)$ s.t. $|S| \leq k$.

I am wondering if there are some references discussing approximation algorithms regarding this problem.

The reference I can find now discussed a similar problem: minimize a non-decreasing submodular function under (lower bound) cardinality constraint (i.e., $|S| \leq k$). But it is not obvious to me how to adapt the result to the previous problem.

Edit: the exact form of $f$ is known.

**Tags:** optimization, submodularity
> **Comments:**
> **username_1**: How is the function $f$ specified? If it is given as an oracle, then you need to look at all $k$-element subsets in the worst case: Assume that $f(S)=1$ if $|S|\le k-1$ and $f(S)=0$ for $|S|\ge k+1$, and assume that $f(S)=1$ for all $S$ with $|S|=k$ with a single exception $T$ with $f(T)=0$. How do you detect the subset $T$?  
> **username_2**: For a set function $g$, let $f(S’) := g(S \setminus S’)$. Then $f$ is submodular nonincreasing iff $g$ is submodular nondecreasing, and a cardinality $k$ upper bound on $S’$ equals a cardinality $|S|-k$ lower bound on $S \setminus S’$, so I think the two problems are equivalent.  
> **username_2**: If you add in the constraint that $f$ is nonnegative, this becomes (effectively) the problem discussed in the third to last paragraph of Sec 1.3 of Svitkina and Fleischer https://arxiv.org/pdf/0805.1071.pdf . Non-increasingness can be assumed w.l.o.g.  
> **username_0**: @Gamow, the exact form of $f$ is known.  

---

## 1 answers

### Answer by username_3 on 2018-09-01. Score: 1

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

> **Comments:**
> **username_2**: I think the author meant to specify that $f$ is submodular. Though not in the body, (s)he says as much in the title. You can still pull off a similar construction.  
> **username_0**: Sorry, I forgot the "submodular" condition in the body.  

---

