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.
• 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 Aug 26 '17 at 21:01
• @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 Aug 27 '17 at 2:18
• @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 Aug 28 '17 at 0:08