A polynomial time approximation scheme (PTAS) for an optimization problem $A$ is an algorithm that on input an instance of $A$ and $\epsilon > 0$ finds a $(1+\epsilon)$-approximate solution in time that is polynomial for each fixed $\epsilon$. Typical running times are $n^{O(1/\epsilon)}$ or $2^{1/\epsilon^{O(1)}} n$. While algorithms of the ... more >>>