4
$\begingroup$

Suppose we have an approximation algorithm to some maximization problem, that returns a solution with value $(1-\epsilon)*OPT$.

  • If the runtime of the algorithm is polynomial in the input size and $1/\epsilon$, then it is called an FPTAS.
  • If the runtime is polynomial in the input size and $\log(1/\epsilon)$, then the algorithm is called polynomial, since $\log(1/\epsilon)$ is the size of the binary representation of $\epsilon$.

My question: are there any algorithms that are "in between" these cases? That is: is there an approximation algorithm with runtime complexity $f(1/\epsilon)$, where $f(x)$ is asymptotically larger than any polynomial of $\log(x)$, but smaller than $x^r$ for any $r>0$?

EDIT: an example of such a function (mentioned in the comments by Discrete Lizard) is $f(x) := 2^{\sqrt{\log{x}}}$. Is there an approximation algorithm with runtime complexity $2^{\sqrt{\log{(1/ \epsilon)}}}$?

$\endgroup$
3
  • 4
    $\begingroup$ I think one such function would be e.g. $2^{\sqrt{\log n}}$. This page on quasi-polynomial functions seems related. ( Of course, $2^{O((\log n)^c)}$ is super-polynomial for c>1, but sub-polynomial for 0<c<1. ) $\endgroup$
    – Discrete lizard
    Jan 31 at 14:25
  • $\begingroup$ @Discretelizard thanks! Do you know if there are any approximation algorithms with run-time in $O(2^{\sqrt{\log(1/\epsilon)}})$? These algorithms would be better than FPTAS but worse than P. $\endgroup$ Mar 7 at 19:18
  • 1
    $\begingroup$ I don't know. I do not even know of an algorithm with this factor in the running time for any parameter. I've only seen quasi-polynomial functions of the super-polynomial type in a running time. $\endgroup$
    – Discrete lizard
    Mar 7 at 21:30

1 Answer 1

-1
$\begingroup$

$\sqrt(n)$. The smallest function polynomial in n is $c \cdot n$ for some $c > 0$.

$\endgroup$
1
  • $\begingroup$ When I wrote "polynomial" I should have written "$n^r$ for some $r>0$" - clarified the question $\endgroup$ Mar 8 at 10:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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