Maximizing a monotone supermodular function s.t. cardinality

Question

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

Answer 1

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.