What is the difference between approximation schemes and approximation algorithms?
Why do we study approximation schemes?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ take a look at this reference page 3. there is a precise definition of algorithms and schemes . win.tue.nl/~gwoegi/AC-2015/ptas.pdf $\endgroup$– Fellow InstituteOfMathophileDec 8, 2021 at 3:21
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
In theoretical computer science, an approximation algorithm is an algorithm that guarantees a certain approximation ratio $\rho$, and an approximation scheme is a (uniform) collection of algorithms that guarantees several different approximation ratios. Since the collection is uniform (all the algorithms look the same but with different parameters), you can also think of an approximation scheme as an algorithm with an auxiliary parameter $\rho$ which then guarantees an approximation ratio of $\rho$; the close $\rho$ is to $1$, the harder the algorithm would have to work, and not all $\rho$ are valid inputs. For example, usually you need $\rho \neq 1$. If the scheme works for $\rho$ arbitrarily close to $1$, and furthermore the scheme is polynomial time (for each $\rho$ separately), then it is a polynomial time approximation scheme (PTAS).
answered Sep 6, 2013 at 12:37
$\begingroup$
$\endgroup$
There is no real difference between approximation "schemes" and "algorithms". The first is in my experience used when talking about algorithms that provide abitrarily good approximations, the second is used for algorithms with a constant or worse approximation factor.
We study approximation algorithms because some problems are infeasible to solve exactly. Take for example the Traveling Salesman problem, where you want to find a shortest tour that visits each city in a country exactly once. Solving it exactly is NP-hard, but finding a solution that is at most 3/2 times as long as the shortest one is fairly easy.
