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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.