patternMinor
Meaning behind 1/ϵ in FPTAS
Viewed 0 times
meaningfptasbehind
Problem
I am currently learning about FPTAS and PTAS but do not understand what the definition of FPTAS.
A fully polynomial time approximation scheme (FPTAS) for problem $X$ is an approximation scheme whose time complexity is polynomial in the input size and also polynomial in $1/\epsilon$.
In this explanation, what does the $\epsilon$ stand for?
A fully polynomial time approximation scheme (FPTAS) for problem $X$ is an approximation scheme whose time complexity is polynomial in the input size and also polynomial in $1/\epsilon$.
In this explanation, what does the $\epsilon$ stand for?
Solution
Suppose that your problem is a minimization problem: on instance $I$, you output a solution $O$ which should minimize some function $f(O)$. We say that an algorithm is a $(1+\epsilon)$-approximation if on instance $I$ it outputs a solution $S$ which satisfies
$$ f(S) \leq (1+\epsilon) f(O) $$
for an optimal solution $O$. We also say that $S$ is a $(1+\epsilon)$-approximate solution.
An FPTAS is an algorithm that gets as input an instance of size $n$ and a number $\epsilon>0$ (let's not worry about how $\epsilon$ is represented), returns a $(1+\epsilon)$-approximate solution, and runs in time $O(n^C (1/\epsilon)^D)$ for some constants $C,D>0$.
Given an FPTAS, you can extract a polynomial time $(1+\epsilon)$-approximation algorithm for any $\epsilon > 0$; furthermore, the dependence of the running time on $\epsilon$ is polynomial (in $1/\epsilon$).
A PTAS, in contrast, is an algorithm gets as input an instance of size $n$ and a number $\epsilon>0$, returns a $(1+\epsilon)$-approximate solution, and for any fixed $\epsilon > 0$, runs in polynomial time. That is, for every $\epsilon > 0$ there exist constants $A_\epsilon,C_\epsilon$ such that the running time of the algorithm is at most $A_\epsilon n^{C_\epsilon}$.
Again, given a PTAS, for any $\epsilon > 0$ we can extract a polynomial time $(1+\epsilon)$-approximation algorithm. This time, however, the dependence of the running time on $\epsilon$ can be arbitrary.
$$ f(S) \leq (1+\epsilon) f(O) $$
for an optimal solution $O$. We also say that $S$ is a $(1+\epsilon)$-approximate solution.
An FPTAS is an algorithm that gets as input an instance of size $n$ and a number $\epsilon>0$ (let's not worry about how $\epsilon$ is represented), returns a $(1+\epsilon)$-approximate solution, and runs in time $O(n^C (1/\epsilon)^D)$ for some constants $C,D>0$.
Given an FPTAS, you can extract a polynomial time $(1+\epsilon)$-approximation algorithm for any $\epsilon > 0$; furthermore, the dependence of the running time on $\epsilon$ is polynomial (in $1/\epsilon$).
A PTAS, in contrast, is an algorithm gets as input an instance of size $n$ and a number $\epsilon>0$, returns a $(1+\epsilon)$-approximate solution, and for any fixed $\epsilon > 0$, runs in polynomial time. That is, for every $\epsilon > 0$ there exist constants $A_\epsilon,C_\epsilon$ such that the running time of the algorithm is at most $A_\epsilon n^{C_\epsilon}$.
Again, given a PTAS, for any $\epsilon > 0$ we can extract a polynomial time $(1+\epsilon)$-approximation algorithm. This time, however, the dependence of the running time on $\epsilon$ can be arbitrary.
Context
StackExchange Computer Science Q#59815, answer score: 6
Revisions (0)
No revisions yet.