4
$\begingroup$

I've tried to comb the literature and seen a lot of references to results that almost but don't quite seem to address this.

Question: Is it known to be true or is there a hardness result contradicting that, for a monotone non-decreasing supermodular $f$, there is a polynomial-time constant-factor approximation algorithm for maximizing $f$ subject to a maximum cardinality constraint?

Background: Given a ground set $U$ of items, $f: 2^U \to \mathbb{R}_{+}$ is supermodular if for all subsets $A,B$ of $U$, we have $f(A) + f(B) \leq f(A \cup B) + f(A \cap B)$. It is monotone non-decreasing if $S \subseteq S' \implies f(S) \leq f(S')$. A maximum cardinality constraint means to maximize $f(S)$ over all subsets $S$ of size at most $k$, where $k$ is given as input.

My current understanding: This problem seems under-studied because supermodular maximization is equivalent to submodular minimization, so people focus on the latter. Submodular minimization subject to a smallest-size cardinality constraint (i.e. $|S| \geq k$) has a very strong lower bound[1].

But there are several issues in transferring such bounds. (1) It is not clear how the notion of approximation factor would transfer (I'm assuming my supermodular function is nonnegative so the transformation would be always negative...). (2) I'm assuming my supermodular function is montone increasing, whereas it seems nobody has been motivated to study the case of negative decreasing submodular minimization. (3) In this particular example, the cardinality constraint "goes the wrong way".

For a different example approach, you might try to reason as follows. The clique problem (find a clique of size k) is hard, and in fact, known to be inapproximable, hence my objective is inapproximable. However, when you think about the supermodular objective function for clique, it would be "find the set of at most $k$ vertices having the most edges in their induced subgraph", whereas the inapproximability result applies to "find the largest clique of size at most $k$". And I don't see a hardness result anywhere for the correct objective. The same kind of issue seems to go for planted clique and densest $k$-subgraph.

In short, it seems that it would be very surprising to have an approximation, but nobody has bothered to prove this in so many words (though actually for all I know, an efficient approximation algorithm exists).

[1] Svitkeina, Fleisher 2008 http://arxiv.org/abs/0805.1071

$\endgroup$
  • 1
    $\begingroup$ Densest k-subgraph is considered likely to be hard. There is some evidence for that. However, as you said, a formal proof for the general setting of supermodular functions has not been shown and it may in fact be easier to do. $\endgroup$ – Chandra Chekuri Mar 3 '16 at 14:02
  • $\begingroup$ @ChandraChekuri thanks for commenting! But am I right that even if densest k-subgraph is hard to approximate, it doesn't seem to immediately imply hardness for approximate supermodular maximization? (the problem I see is that the natural supermodular function is number of edges, not density) $\endgroup$ – usul Mar 3 '16 at 17:17
4
$\begingroup$

I think this is an example showing no kind of approximation is possible except with exponential$(k)$ value queries.

Let $f(S) = 0$ if $|S| \leq k$, otherwise $f(S) = |S| - k$. Now pick a special set $S^*$ uniformly at random from all sets of size $k$, and let $f(S^*) = 0.5$.

I'm claiming that this function is supermodular because every element initially has $0$ marginal value, then possibly $0.5$, then $1$ thereafter. So marginal value of any element only increases in a superset.

$S^*$ maximizes the function subject to a cardinality constraint of $k$, with an objective value of $0.5$.

Meanwhile any algorithm making subexponentially many value queries will be unable (except with tiny probability) to find a feasible set with nonzero value.

$\endgroup$
  • $\begingroup$ Seems correct. Nice. $\endgroup$ – Chandra Chekuri Mar 4 '16 at 0:21
  • $\begingroup$ Thank you! I will accept tomorrow if there are no further comments, references, or answers. $\endgroup$ – usul Mar 4 '16 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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