2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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$? $\endgroup$
    – Gamow
    Commented Sep 2, 2018 at 4:07
  • $\begingroup$ 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. $\endgroup$
    – Yonatan N
    Commented Sep 2, 2018 at 9:07
  • $\begingroup$ 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 arxiv.org/pdf/0805.1071.pdf . Non-increasingness can be assumed w.l.o.g. $\endgroup$
    – Yonatan N
    Commented Sep 2, 2018 at 9:32
  • $\begingroup$ @Gamow, the exact form of $f$ is known. $\endgroup$
    – Paradox
    Commented Sep 2, 2018 at 15:32

1 Answer 1

Reset to default
1
$\begingroup$

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$, and with arbitrary values on the sets of cardinality $k$, and $-\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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Yonatan N
    Commented Sep 2, 2018 at 9:30
  • $\begingroup$ Sorry, I forgot the "submodular" condition in the body. $\endgroup$
    – Paradox
    Commented Sep 2, 2018 at 15:29

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.