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 '20 at 7:38
  • $\begingroup$ @user3680510 I think it was a PTAS if there was no $\log$ in the power. $\endgroup$
    – Mostafa
    Apr 16 '20 at 9:33
  • $\begingroup$ Nevertheless, this should be better then a Fully Polynomial Time Approximation Scheme, right? $\endgroup$
    – C Marius
    Apr 16 '20 at 10:33
  • $\begingroup$ @user3680510 Seems like your comment should be an answer? (I'm not vouching for its correctness, just its purpose.) $\endgroup$
    – LarrySnyder610
    Apr 16 '20 at 12:49
  • $\begingroup$ @Mostafa for the definition of PTAS this does not matter. $\endgroup$ Apr 16 '20 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).


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.