HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaModerate

Difference between approximation scheme and approximation algorithm?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
schemeapproximationdifferencealgorithmbetweenand

Problem

What is the difference between approximation schemes and approximation algorithms?

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.