7
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ It is a en.wikipedia.org/wiki/Polynomial-time_approximation_scheme. $\endgroup$
    – user3680510
    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$
    – LarrySnyder610
    Apr 16, 2020 at 12:49
  • $\begingroup$ @Mostafa for the definition of PTAS this does not matter. $\endgroup$
    – user3680510
    Apr 16, 2020 at 15:41

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

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

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