2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – usul Aug 26 '17 at 21:01
  • 1
    $\begingroup$ @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. $\endgroup$ – Chandra Chekuri Aug 27 '17 at 2:18
  • $\begingroup$ @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? $\endgroup$ – karmanaut Aug 28 '17 at 0:08
  • $\begingroup$ Cross-posted: math.stackexchange.com/q/2406245/14578, cstheory.stackexchange.com/q/38914/5038. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Sep 21 '17 at 21:51

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.