# Can this algorithm be considered polynomial?

Let us assume that an optimization algorithm requires $$\mathcal{O}(n^{\log1/\epsilon})$$ flops to find a solution $$\bar{X}$$ such that $$\| \bar{X} - X^{\star}\| \leq \epsilon$$ where $$\epsilon < 1$$ and $$X^{\star}$$ is the true optimum point.

What kind of algorithm is this? Can it be considered polynomial?

• Apr 16, 2020 at 7:38
• @user3680510 I think it was a PTAS if there was no $\log$ in the power. Apr 16, 2020 at 9:33
• Nevertheless, this should be better then a Fully Polynomial Time Approximation Scheme, right? Apr 16, 2020 at 10:33
• @user3680510 Seems like your comment should be an answer? (I'm not vouching for its correctness, just its purpose.) Apr 16, 2020 at 12:49
• @Mostafa for the definition of PTAS this does not matter. Apr 16, 2020 at 15:41

It is a polynomial-time approximation scheme (see Polynomial-time Approximation Scheme). This can be seen since when you fix $$\epsilon$$, the running time is polynomial in $$n$$. It is however no FPTAS, since this would require that its running time is in $$O((n/\epsilon)^C)$$ for some fixed constant $$C$$ (see this post).