<p>I am trying to understand whether a monotone and subadditive function $f(S), S \subseteq 2^{[n]}$ and $ f : 2^{[n]} \rightarrow R_{\geq0}$ can be represented using an additive function $\hat{f}(S) = \sum_{i \in S} w_i$. In other words, is it possible to approximate $f$ for all $S$ by finding the value of the weights $w_i$?</p>

<p>The best I can do is the following : $\hat{f} = \sum_{i \in S} \frac{f({i})}{n}$ which can be shown to be $\frac{f(S)}{n} \leq \hat{f}(S) \leq f(S)$ i.e an $n-$approximation. Note that I just need to argue about existence of such a function and not the construction. There are known results on how this is impossible to do in subexponential queries using an oracle that gives you access to $f$ and queries are of the form $f(S)$ for any $S$. I am looking for lower bounds assuming infinite computational power. Is it possible to show that this is tight and we cannot hope to have a better function?</p>

<p>My intuition is that a subadditive function is still pretty linear and a bad instance would be when the values of all sets of fixed size (say $k$) vary wildly rather than being a constant/additive/linearly.</p>

<p>Any reference about representing function using additive linear functions will be very helpful!</p>

CC BY-SA 3.0
2017-08-26T21:01:38.377Z
If we consider $f(S) = \min(|S|, n/2)$, I don't think an additive function can approximate it better than $\Omega(n)$ or at all of the cases $S=0, |S|=n/2, |S|=n$.
usul
CC BY-SA 3.0
2017-08-27T02:18:52.410Z
@usual - your function is easy to approximate to within a factor of 2 by setting $w_i = 1$ for each $i$. On the other hand if you take the function $f(S) = \min(|S|, \sqrt{n})$ then one can show that no additive function can approximate this to within a $\sqrt{n}$ factor. Btw, this is not only subadditive but a rather simple submodular function.
Chandra Chekuri
CC BY-SA 3.0
2017-08-28T00:08:02.463Z
@ChandraChekuri I think I can strengthen this even further. Suppose that I want to find an $n-$approximation. Consider the constant function $f(X) = c$ and let $\hat{f}(S) = \sum_i w_i f(\{i\})$. Setting $S$ to be all singletons, we get $\frac{1}{n} \leq w_i \leq 1$. Setting $S = \{1, \dots, n\}$, we have $\frac{1}{n} \leq \sum_i w_i \leq 1$. Both these equations are satisfied if and only if each $w_i = \frac{1}{n}$ meaning no other function can approximate them to with $n$ factor. Does this make sense?
karmanaut
CC BY-SA 3.0
2017-09-21T21:51:56.490Z
Cross-posted: https://math.stackexchange.com/q/2406245/14578, https://cstheory.stackexchange.com/q/38914/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted.
D.W.
<approximation-algorithms><approximation-hardness><submodularity>
On the impossibility of representing/approximating subadditive function using additive functions
karmanaut
# On the impossibility of representing/approximating subadditive function using additive functions

(Asked by: username_0 on 2017-08-25)

I am trying to understand whether a monotone and subadditive function $f(S), S \subseteq 2^{[n]}$ and $ f : 2^{[n]} \rightarrow R\_{\geq0}$ can be represented using an additive function $\hat{f}(S) = \sum\_{i \in S} w\_i$. In other words, is it possible to approximate $f$ for all $S$ by finding the value of the weights $w\_i$?

The best I can do is the following : $\hat{f} = \sum\_{i \in S} \frac{f({i})}{n}$ which can be shown to be $\frac{f(S)}{n} \leq \hat{f}(S) \leq f(S)$ i.e an $n-$approximation. Note that I just need to argue about existence of such a function and not the construction. There are known results on how this is impossible to do in subexponential queries using an oracle that gives you access to $f$ and queries are of the form $f(S)$ for any $S$. I am looking for lower bounds assuming infinite computational power. Is it possible to show that this is tight and we cannot hope to have a better function?

My intuition is that a subadditive function is still pretty linear and a bad instance would be when the values of all sets of fixed size (say $k$) vary wildly rather than being a constant/additive/linearly.

Any reference about representing function using additive linear functions will be very helpful!

**Tags:** approximation-algorithms, approximation-hardness, submodularity

> **Comments:**
> **username_1**: If we consider $f(S) = \min(|S|, n/2)$, I don't think an additive function can approximate it better than $\Omega(n)$ or at all of the cases $S=0, |S|=n/2, |S|=n$.  
> **username_2**: @usual - your function is easy to approximate to within a factor of 2 by setting $w_i = 1$ for each $i$. On the other hand if you take the function $f(S) = \min(|S|, \sqrt{n})$ then one can show that no additive function can approximate this to within a $\sqrt{n}$ factor. Btw, this is not only subadditive but a rather simple submodular function.  
> **username_0**: @ChandraChekuri I think I can strengthen this even further. Suppose that I want to find an $n-$approximation. Consider the constant function $f(X) = c$ and let $\hat{f}(S) = \sum_i w_i f(\{i\})$. Setting $S$ to be all singletons, we get $\frac{1}{n} \leq w_i \leq 1$. Setting $S = \{1, \dots, n\}$, we have $\frac{1}{n} \leq \sum_i w_i \leq 1$. Both these equations are satisfied if and only if each $w_i = \frac{1}{n}$ meaning no other function can approximate them to with $n$ factor. Does this make sense?  
> **username_3**: Cross-posted: https://math.stackexchange.com/q/2406245/14578, https://cstheory.stackexchange.com/q/38914/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted.  

---

## 0 answers

