gotchaModerate
Difference between approximation scheme and approximation algorithm?
Viewed 0 times
schemeapproximationdifferencealgorithmbetweenand
Problem
What is the difference between approximation schemes and approximation algorithms?
Why do we study approximation schemes?
Why do we study approximation schemes?
Solution
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).
Context
StackExchange Computer Science Q#14162, answer score: 10
Revisions (0)
No revisions yet.