# Approximation algorithm with runtime complexity between poly(log(1/eps)) and poly(1/eps)?

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)}}}$$?

• 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. ) Jan 31 at 14:25
• @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. Mar 7 at 19:18
• 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. Mar 7 at 21:30

$$\sqrt(n)$$. The smallest function polynomial in n is $$c \cdot n$$ for some $$c > 0$$.
• When I wrote "polynomial" I should have written "$n^r$ for some $r>0$" - clarified the question Mar 8 at 10:49