I have a randomized approximation algorithm which can be tuned by selecting the randomization probabilities. I found out that:

  • For any $\epsilon >0$, there are probabilities for which the approximation factor is $O(n^\epsilon)$.
  • There are probabilities for which the approximation factor is $O(\ln n)$ (smaller factor is better).

I know that $O(\ln n)$ is asymptotic smallerer than any $O(n^\epsilon)$ when $\epsilon$ is fixed, but here $\epsilon$ can be made arbitrarily small, so I don't know, which of these two bounds is considered better? Specifically:

A. Theoretically, which of these two bounds should I report in a paper? Is the bound $O(n^\epsilon)$ interesting, or is it considered useless given the logarithmic bound?

B. Practically, if I have to run the algorithm on very-big-data, with no possibility of making tests in advance, which tuning is better?

(Just to get some feeling, I compared $n^{0.1}$ with $\ln n$. It turns out that $n^{0.1}$ is better even for very large $n$ - they become equal at about $n=4 \cdot 10^{15}$)

  • 1
    $\begingroup$ Depends on what your narrative is. Asymptotics are everything? The logarithmic bound. Real efficiency is a concern? The polynomial. However, if you can express $\epsilon$ as a function of $n$, say $\epsilon = 1/\ln(n)$ -- that is, make the algorithm adaptive, you can be better asymptotically as well. Other than that, why not report both? $\endgroup$ – Raphael Apr 22 '15 at 14:09
  • $\begingroup$ In fact, $\log n = O(n^{\epsilon})$ for every $\epsilon > 0$. Even more, $\log n = O(n^{\epsilon})$ for $\epsilon = \log\log n/\log n$. $\endgroup$ – Yuval Filmus Apr 22 '15 at 14:18
  • $\begingroup$ Another issue is that there are hidden constants – it could be $\ln n$ against $100n^{0.1}$, for example. The constants affect the cutoff. $\endgroup$ – Yuval Filmus Apr 22 '15 at 14:45
  • 1
    $\begingroup$ @Raphael's suggestion made a lot of sense according to what I asked, but on the same time, it seemed too good to be true that I can get a constant factor. So, following Yuval's suggestion, I calculated the constants and found it that the polynomial bound has a $1+1/\epsilon$ constant, which immediately makes it worse than the logarithmic bound, as it should be :) I learned my lesson. $\endgroup$ – Erel Segal-Halevi Apr 24 '15 at 12:29

Since $\log n = O(n^{\epsilon})$ for an $\epsilon > 0$, if you can prove an approximation ratio of $O(\log n)$, then approximation ratios of $O(n^{\epsilon})$ (for any $\epsilon > 0$) immediately follow. You should always prove the best approximation ratio that you can, unless:

  • The best approximation ratio holds only in expectation, and some other approximation ratio holds with high probability.
  • You have several incomparable approximation ratios (this is more common in expressions involving more than one parameter).

That is, your worse guarantee needs to have some advantage over your better guarantee for you to report both.

Regarding practical performance, you are highlighting the fact that asymptotic performance can be misleading when it comes to evaluating algorithms in practice. The most well-known instance is probably "fast" matrix multiplication, which is usually slower than the trivial algorithm. Here you have two options:

  • Prove non-asymptotic guarantees on the approximation ratio, say $100\log n$ and $(2/\epsilon)n^{\epsilon}$. This allows you to obtain concrete guarantees for every $n$.

  • Do experiments. The experiments reveal the actual approximation ratio on the average. If you can fit your results to a nice function, you can say that empirically, the average approximation ratio is (say) $10\log n$, though in the worst case all you know is (say) $100\log n$. Experiments, however, are not so welcome in theoretical papers, unfortunately.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.