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?

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

1 Answer 1


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).


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.