patternMinor
FPTAS definition
Viewed 0 times
definitionfptasstackoverflow
Problem
I read that a fully polynomial time approximation scheme (FPTAS) has time complexity polynomial in the input size and also polynomial in $1/\epsilon$. However, this leaves some ambiguity.
For example, $T(n,1/\epsilon)=\min(n^{1/\epsilon},(1/\epsilon)^n)$ is both polynomial in $n$ (when holding $1/\epsilon$ constant) and polynomial in $1/\epsilon$ (when holding $n$ constant). But $T$ is not polynomial in $n/\epsilon$ or $(n+1/\epsilon)$ because $\sqrt x^\sqrt x$ and $(x/2)^{x/2}$ aren't bounded by polynomials.
Does this mean an algorithm with running time $T$ isn't an FTPAS, and perhaps a better definition would be that it has to be polynomial in $n+1/\epsilon$?
For example, $T(n,1/\epsilon)=\min(n^{1/\epsilon},(1/\epsilon)^n)$ is both polynomial in $n$ (when holding $1/\epsilon$ constant) and polynomial in $1/\epsilon$ (when holding $n$ constant). But $T$ is not polynomial in $n/\epsilon$ or $(n+1/\epsilon)$ because $\sqrt x^\sqrt x$ and $(x/2)^{x/2}$ aren't bounded by polynomials.
Does this mean an algorithm with running time $T$ isn't an FTPAS, and perhaps a better definition would be that it has to be polynomial in $n+1/\epsilon$?
Solution
The standard definition is incredibly ambiguous, since it is not clear what "polynomial in $n$ and in $1/\epsilon$" means. Judging from examples, it means $O(n^C(1/\epsilon)^D)$ for some constants $C,D$. Without loss of generality, $C=D$, and then we get the simpler definition $O((n/\epsilon)^C)$.
Context
StackExchange Computer Science Q#95988, answer score: 2
Revisions (0)
No revisions yet.