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

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

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

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

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

CC BY-SA 3.0
2016-03-04T00:21:15.137Z
Seems correct. Nice.
Chandra Chekuri
CC BY-SA 3.0
2016-03-04T14:23:37.593Z
Thank you! I will accept tomorrow if there are no further comments, references, or answers.
usul
CC BY-SA 3.0
2016-03-03T21:05:20.983Z
2016-03-03T21:05:20.983Z
usul
<p>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.</p>

<blockquote>
  <p><strong>Question:</strong> 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?</p>
</blockquote>

<p><strong>Background:</strong> Given a ground set $U$ of items, $f: 2^U \to \mathbb{R}_{+}$ is <em>supermodular</em> 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 <em>monotone non-decreasing</em> 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.</p>

<p><strong>My current understanding:</strong> 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].</p>

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

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

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

<p>[1] Svitkeina, Fleisher 2008 <a href="http://arxiv.org/abs/0805.1071">http://arxiv.org/abs/0805.1071</a></p>

CC BY-SA 3.0
2016-03-03T14:02:58.503Z
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.
Chandra Chekuri
CC BY-SA 3.0
2016-03-03T17:17:38.983Z
@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)
usul
<ds.algorithms><approximation-algorithms><optimization><approximation-hardness><submodularity>
Maximizing a monotone supermodular function s.t. cardinality
usul
# Maximizing a monotone supermodular function s.t. cardinality

(Asked by: username_0 on 2016-03-03)

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>

**Tags:** ds.algorithms, approximation-algorithms, optimization, approximation-hardness, submodularity

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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)  

---

## 1 answers

### Answer by username_0 on 2016-03-03. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_1**: Seems correct. Nice.  
> **username_0**: Thank you! I will accept tomorrow if there are no further comments, references, or answers.  

---

