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?

$\endgroup$
  • 1
    $\begingroup$ It is a en.wikipedia.org/wiki/Polynomial-time_approximation_scheme. $\endgroup$ – user3680510 Apr 16 at 7:38
  • $\begingroup$ @user3680510 I think it was a PTAS if there was no $\log$ in the power. $\endgroup$ – Mostafa Apr 16 at 9:33
  • $\begingroup$ Nevertheless, this should be better then a Fully Polynomial Time Approximation Scheme, right? $\endgroup$ – C Marius Apr 16 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 at 12:49
  • $\begingroup$ @Mostafa for the definition of PTAS this does not matter. $\endgroup$ – user3680510 Apr 16 at 15:41
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, privacy policy and cookie policy

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