Approximation Scheme

computation

Definition

Approximation Scheme

Let $\Pi$ be an optimisation problem with objective function $f_{\Pi }$.

An algorithm $\mathcal{A}$ is an approximation scheme for $\Pi$ if, on each input $(I,\epsilon )$ where $I$ is an instance of $\Pi$ and $\epsilon >0$ is an error parameter, it returns a feasible solution $s$ such that:

Minimisation $\Pi$ is a minimisation problem, then

$$f_{\Pi }(I,s)\le (1+\epsilon )\cdot \mathrm{OPT}(I).$$

Maximisation $\Pi$ is a maximisation problem, then

$$f_{\Pi }(I,s)\ge (1-\epsilon )\cdot \mathrm{OPT}(I).$$

For every fixed $\epsilon$, the approximation ratio can be made arbitrarily close to $1$.

Intuition

What changes with $\epsilon$

A factor-delta approximation algorithm gives one fixed guarantee: for every input, it returns a solution within the stated factor of optimum.

An approximation scheme is different. It takes an error parameter $\epsilon$ as part of the input. The algorithm then adapts its behaviour to that requested accuracy.

So the scheme does not say only that “this algorithm is approximately good”. It says: if I ask for a smaller error, I should get a better approximation, usually at the cost of a slower running time.

In short, a factor-$\delta$ approximation algorithm is about a guarantee, while an approximation scheme is about a tunable method for trading time against accuracy.

Allowed Error

The parameter $\epsilon$ controls the allowed error.

• Smaller $\epsilon$ means a better approximation.
• Larger $\epsilon$ allows a weaker guarantee.

The definition itself does not restrict the running time. That is done by stronger notions such as PTAS, EPTAS, and FPTAS.

Hierarchy

The main approximation-scheme classes form the chain:

FPTAS $⊊$ EPTAS $⊊$ PTAS $⊊$ approximation scheme

Polynomial-time

Definition

Polynomial-time Approximation Scheme

An approximation scheme $\mathcal{A}$ is a polynomial-time approximation scheme if, for every fixed constant $\epsilon >0$, the running time of $\mathcal{A}$ is polynomial in the input size $|I|$.

Equivalently,

$$T_{\mathcal{A}}(|I|,\epsilon )=|I{|}^{g(\epsilon )}$$

for some function $g$ that depends only on $\epsilon$.

Link to original

Efficient Polynomial-time

Definition

Efficient Polynomial-time Approximation Scheme

An approximation scheme $\mathcal{A}$ is called an efficient polynomial-time approximation scheme if its running time has the form

$$T_{\mathcal{A}}(|I|,\epsilon )=f\left(\frac{1}{\epsilon }\right)\cdot |I{|}^{O(1)}$$

for some function $f$ that depends only on $\epsilon$.

Equivalently, an EPTAS is a PTAS whose polynomial degree in $|I|$ does not depend on $\epsilon$.

Link to original

Fully Polynomial-time

Definition

Fully Polynomial-time Approximation Scheme

An approximation scheme $\mathcal{A}$ is called a fully polynomial-time approximation scheme if its running time is polynomial in both the input size $|I|$ and $\frac{1}{\epsilon }$, i.e.:

$$T_{\mathcal{A}}(|I|,\epsilon )={\left(\frac{|I|}{\epsilon }\right)}^{O(1)}.$$

Equivalently, an FPTAS is a PTAS whose dependence on the error parameter is also polynomial.

Link to original