Principles of approximation algorithms¶

Part 5 · Approximation algorithms · Chapter 34 · Lecture notes, volume 5 (PDF) · Slides · Exercises: Principles · App: Tight instances

Prerequisites

From this module, the chapter «Heuristic algorithms: definitions»: heuristic algorithms, feasible solutions and the value of the solution returned by a heuristic algorithm.
From this module, the chapters on the combinatorial optimization problems: instances, optimal solutions and the optimal value $z(I)$ of an instance $I$.

Objectives

At the end of this chapter you will be able to:

compute the performance ratio, the additive error and the relative error of a heuristic algorithm on an instance, for minimization and maximization problems;
state when a number is a relative or an additive performance guarantee, and when it is tight;
prove that a guarantee is tight by exhibiting an instance, or a sequence of instances;
define an approximation scheme, a PTAS and an FPTAS, and translate the accuracy $\varepsilon$ into a performance guarantee.

34.1 Approximation algorithms¶

Definition 34.1: heuristic value

Let $\mathscr{A}$ be a heuristic algorithm for an optimization problem $\mathscr{P}$. For every instance $I$ of $\mathscr{P}$:

$z(I)$ is the optimal value of $\mathscr{P}$ on $I$ (assumed positive);
$\mathscr{A}(I)$ is the heuristic value, i.e., the objective value of the feasible solution returned by $\mathscr{A}$ on $I$ (assumed positive).

We assume that $\mathscr{A}$ always outputs a feasible solution. Hence, for every instance $I$,

\[ \begin{cases} \mathscr{A}(I)\ge z(I)\ \ \text{and}\ \ \dfrac{\mathscr{A}(I)}{z(I)} \ge 1 & \quad \text{if $\mathscr{P}$ is a minimization problem,}\\[2.5ex] \mathscr{A}(I)\le z(I)\ \ \text{and}\ \ \dfrac{z(I)}{\mathscr{A}(I)} \ge 1 & \quad \text{if $\mathscr{P}$ is a maximization problem.} \end{cases} \]

In general, a heuristic algorithm may sometimes generate solutions with an almost optimal value, but in other cases it may produce significantly inferior solutions. Accordingly, we are interested in “measuring” (whenever possible) the quality of the solutions provided by a heuristic algorithm.

We adopt a worst-case behaviour point of view: we evaluate a heuristic algorithm by looking at the largest possible deviation, over all instances, between the heuristic value and the optimal value.
There are two standard ways to measure this deviation:
1. Relative performance guarantee (multiplicative guarantee): in this case we measure the quality of the heuristic solution by looking at the relative error, that is, how far the heuristic value is from the optimum in relative terms, using ratios.
2. Absolute performance guarantee (additive guarantee): in this case we measure the quality of the heuristic solution by looking at the absolute error, that is, the difference between the heuristic value and the optimal value.

34.1.1 Relative performance guarantee¶

Definition 34.2: performance ratio

The performance ratio of $\mathscr{A}$ on an instance $I$ is

\[ \begin{cases} \dfrac{\mathscr{A}(I)}{z(I)} & \quad \text{if $\mathscr{P}$ is a minimization problem,}\\[2.5ex] \dfrac{z(I)}{\mathscr{A}(I)} & \quad \text{if $\mathscr{P}$ is a maximization problem.} \end{cases} \]

Under the feasibility assumption, the performance ratio is at least $1$ for every instance $I$.

Definition 34.3: $\alpha$-approximation algorithm

A heuristic algorithm $\mathscr{A}$ for an optimization problem $\mathscr{P}$ is an $\alpha$-approximation algorithm if there exists a constant $\alpha \in [1,+\infty)$ such that, for every instance $I$ of $~\mathscr{P}$,

\[ \begin{cases} \dfrac{\mathscr{A}(I)}{z(I)} \le \alpha & \quad \text{if $\mathscr{P}$ is a minimization problem,}\\[2.5ex] \dfrac{z(I)}{\mathscr{A}(I)} \le \alpha & \quad \text{if $\mathscr{P}$ is a maximization problem.} \end{cases} \]

Any such constant $\alpha$ is called a relative performance guarantee of $\mathscr{A}$.

A relative performance guarantee $\alpha$ for $\mathscr{A}$ is tight if no smaller constant $\alpha' < \alpha$ is also a relative performance guarantee for $\mathscr{A}$ (i.e., the same inequalities hold for all instances with $\alpha'$ in place of $\alpha$).
Tightness is usually proved by exhibiting either an instance $I$ for which the performance ratio attains $\alpha$, namely

\[ \frac{\mathscr{A}(I)}{z(I)}=\alpha \ \ \text{(minimization)} \qquad \text{or} \qquad \frac{z(I)}{\mathscr{A}(I)}=\alpha \ \ \text{(maximization),} \]

or a sequence of instances $\{I_n\}$ such that the corresponding performance ratios get arbitrarily close to $\alpha$.

Definition 34.4: Worst-case performance ratio

The worst-case performance ratio of $\mathscr{A}$ is

\[ r(\mathscr{A}) \;=\; \begin{cases} \sup \left\{\, \dfrac{\mathscr{A}(I)}{z(I)} : I \text{ is an instance of } \mathscr{P} \,\right\} & \quad \text{if $\mathscr{P}$ is a minimization problem,}\\[3.0ex] \sup \left\{\, \dfrac{z(I)}{\mathscr{A}(I)} : I \text{ is an instance of } \mathscr{P} \,\right\} & \quad \text{if $\mathscr{P}$ is a maximization problem.} \end{cases} \]

The value $r(\mathscr{A})$ is the smallest constant $\alpha$ for which $\mathscr{A}$ is an $\alpha$-approximation algorithm. The relative performance guarantee $\alpha$ is tight if and only if $\alpha = r(\mathscr{A})$.
If $r(\mathscr{A})<\infty$, then $\mathscr{A}$ admits a finite relative performance guarantee (equivalently, it has a bounded performance ratio). If $r(\mathscr{A})=\infty$, then $\mathscr{A}$ has no relative worst-case guarantee.
Terminology used in the literature
- a finite relative performance guarantee $\alpha$ is also called an approximation factor (or approximation guarantee)
- an $\alpha$-approximation algorithm is also called a constant-factor approximation algorithm
- $r(\mathscr{A})$ is also called the (worst-case) approximation ratio of $\mathscr{A}$

34.1.2 Additive performance guarantee¶

The additive error (or absolute error) of $\mathscr{A}$ on an instance $I$ is

\[ \begin{cases} \mathscr{A}(I)-z(I) & \text{if $\mathscr{P}$ is a minimization problem,}\\[2ex] z(I)-\mathscr{A}(I) & \text{if $\mathscr{P}$ is a maximization problem.} \end{cases} \]

Under the feasibility assumption, this quantity is non-negative for every instance $I$.

Definition 34.5: $\beta$-additive approximation algorithm

A heuristic algorithm $\mathscr{A}$ for an optimization problem $\mathscr{P}$ is a $\beta$-additive approximation algorithm if there exists a constant $\beta \in [0,+\infty)$ such that, for every instance $I$ of $~\mathscr{P}$,

\[ \begin{cases} \mathscr{A}(I)-z(I) \le \beta & \text{if $\mathscr{P}$ is a minimization problem,}\\[2ex] z(I)-\mathscr{A}(I) \le \beta & \text{if $\mathscr{P}$ is a maximization problem.} \end{cases} \]

Any such constant $\beta$ is called an additive performance guarantee of $\mathscr{A}$.

An additive performance guarantee $\beta$ for $\mathscr{A}$ is tight if no smaller constant $\beta' < \beta$ is also an additive performance guarantee for $\mathscr{A}$.
Tightness is usually proved by exhibiting either an instance $I$ for which the additive error attains $\beta$, namely

\[ \mathscr{A}(I)-z(I)=\beta \ \ \text{(minimization)} \qquad \text{or} \qquad z(I)-\mathscr{A}(I)=\beta \ \ \text{(maximization),} \]

or a sequence of instances $\{I_n\}$ such that the corresponding additive errors get arbitrarily close to $\beta$.

Definition 34.6: Worst-case additive error

The worst-case additive error of $\mathscr{A}$ is

\[ e(\mathscr{A}) \;=\; \begin{cases} \sup \left\{\, \mathscr{A}(I)-z(I) : I \text{ instance of } \mathscr{P} \,\right\} & \text{if $\mathscr{P}$ is a minimization problem,}\\[3.0ex] \sup \left\{\, z(I)-\mathscr{A}(I) : I \text{ instance of } \mathscr{P} \,\right\} & \text{if $\mathscr{P}$ is a maximization problem.} \end{cases} \]

The value $e(\mathscr{A})$ is the smallest constant $\beta$ for which $\mathscr{A}$ is a $\beta$-additive approximation algorithm. The additive performance guarantee $\beta$ is tight if and only if $\beta = e(\mathscr{A})$.
If $e(\mathscr{A})<\infty$, then $\mathscr{A}$ admits a finite additive performance guarantee (equivalently, it has bounded additive error). If $e(\mathscr{A})=\infty$, then $\mathscr{A}$ has no additive (absolute) worst-case guarantee.
Terminology used in the literature
- a finite additive performance guarantee $\beta$ is also called an absolute performance guarantee or an additive approximation guarantee
- $e(\mathscr{A})$ is also called the worst-case absolute (additive) error of $\mathscr{A}$

34.2 Approximation schemes¶

The relative error (also called percentage error) of $\mathscr{A}$ on an instance $I$ is

\[ \begin{cases} \dfrac{\mathscr{A}(I)-z(I)}{z(I)} & \quad \text{if $\mathscr{P}$ is a minimization problem,}\\[2.5ex] \dfrac{z(I)-\mathscr{A}(I)}{z(I)} & \quad \text{if $\mathscr{P}$ is a maximization problem.} \end{cases} \]

Under the feasibility assumption, this quantity is non-negative for every instance $I$, and it is equal to $0$ if and only if $\mathscr{A}(I)=z(I)$.
The relative error divides by the optimal value $z(I)$, and must not be confused with the gap of the chapter «Combinatorial optimization problems», which divides by the lower bound and is never smaller (chapter «Heuristic algorithms: definitions»).

Definition 34.7: Approximation scheme

An approximation scheme for an optimization problem $\mathscr{P}$ is a family of heuristic algorithms $\{\mathscr{A}_{\varepsilon}\}_{\varepsilon \in (0,1)}$ such that, for every $\varepsilon \in (0,1)$ and for every instance $I$ of $\mathscr{P}$,

\[ \begin{cases} \dfrac{\mathscr{A}_{\varepsilon}(I)-z(I)}{z(I)} \le \varepsilon & \text{if $\mathscr{P}$ is a minimization problem,}\\[2.5ex] \dfrac{z(I)-\mathscr{A}_{\varepsilon}(I)}{z(I)} \le \varepsilon & \text{if $\mathscr{P}$ is a maximization problem.} \end{cases} \]

For minimization problems,

\[ \frac{\mathscr{A}_{\varepsilon}(I)-z(I)}{z(I)} \le \varepsilon \qquad \text{for every instance $I$ of $\mathscr{P}$.} \]

implies

\[ \mathscr{A}_{\varepsilon}(I)-z(I)\le \varepsilon\,z(I) \quad \Longleftrightarrow \quad \mathscr{A}_{\varepsilon}(I)\le (1+\varepsilon)\,z(I). \]

Dividing by $z(I)>0$,

\[ \frac{\mathscr{A}_{\varepsilon}(I)}{z(I)}\le 1+\varepsilon \qquad \text{for every instance $I$ of $\mathscr{P}$.} \]

Hence, $\mathscr{A}_{\varepsilon}$ is a $(1+\varepsilon)$-approximation algorithm.
For maximization problems,

\[ \frac{z(I)-\mathscr{A}_{\varepsilon}(I)}{z(I)} \le \varepsilon \qquad \text{for every instance $I$ of $\mathscr{P}$.} \]

implies

\[ z(I)-\mathscr{A}_{\varepsilon}(I)\le \varepsilon\,z(I) \quad \Longleftrightarrow \quad \mathscr{A}_{\varepsilon}(I)\ge (1-\varepsilon)\,z(I). \]

Since $0<\varepsilon<1$ and $z(I)>0$, dividing by $(1-\varepsilon)z(I)$ gives

\[ \frac{z(I)}{\mathscr{A}_{\varepsilon}(I)}\le \frac{1}{1-\varepsilon} \qquad \text{for every instance $I$ of $\mathscr{P}$.} \]

Hence, $\mathscr{A}_{\varepsilon}$ is a $\left(\frac{1}{1-\varepsilon}\right)$-approximation algorithm.

It is quite natural that the running time of an approximation scheme increases as $\varepsilon$ decreases: the smaller the allowed error, the higher the required running time.

The quantity $\frac{1}{\varepsilon}$ is often called the accuracy. Indeed, from the defining inequalities of an approximation scheme we obtain

\[ \frac{\mathscr{A}_{\varepsilon}(I)-z(I)}{z(I)} \le \varepsilon \ \Longrightarrow\ \mathscr{A}_{\varepsilon}(I)-z(I)\le \varepsilon\,z(I) \ \Longrightarrow\ \frac{z(I)}{\mathscr{A}_{\varepsilon}(I)-z(I)} \ge \frac{1}{\varepsilon} \qquad \text{(minimization),} \]

\[ \frac{z(I)-\mathscr{A}_{\varepsilon}(I)}{z(I)} \le \varepsilon \ \Longrightarrow\ z(I)-\mathscr{A}_{\varepsilon}(I)\le \varepsilon\,z(I) \ \Longrightarrow\ \frac{z(I)}{z(I)-\mathscr{A}_{\varepsilon}(I)} \ge \frac{1}{\varepsilon} \qquad \text{(maximization).} \]

In the special case where $\mathscr{A}_{\varepsilon}(I)=z(I)$, the denominators above are zero; in this case we interpret the corresponding fractions as $+\infty$, and the inequalities hold trivially.
Not all approximation schemes are equally useful in practice: we distinguish them according to how the running time depends on the input size and on the accuracy $\frac{1}{\varepsilon}$.

Definition 34.8: Polynomial-time approximation scheme (PTAS)

An approximation scheme $\{\mathscr{A}_{\varepsilon}\}_{\varepsilon\in(0,1)}$ is a polynomial-time approximation scheme if, for every fixed $\varepsilon\in(0,1)$, the running time of $\mathscr{A}_{\varepsilon}$ is polynomial in the size of the instance.

Thus, the running time is polynomial in the input size, but it may grow very fast as $\varepsilon$ decreases (i.e., as the required accuracy increases).

Definition 34.9: Fully polynomial-time approximation scheme (FPTAS)

An approximation scheme $\{\mathscr{A}_{\varepsilon}\}_{\varepsilon\in(0,1)}$ is a fully polynomial-time approximation scheme if the running time of $\mathscr{A}_{\varepsilon}$ is polynomial both in the size of the instance and in the accuracy $\frac{1}{\varepsilon}$.

34.3 Typical mistakes¶

Warning

Inverting the ratio. The performance ratio is $\frac{\mathscr{A}(I)}{z(I)}$ for a minimization problem and $\frac{z(I)}{\mathscr{A}(I)}$ for a maximization problem: in both cases it is at least $1$.
Proving a guarantee with examples. An instance on which the ratio equals $\alpha$ shows that no constant below $\alpha$ is a guarantee, but it does not prove that $\alpha$ is one: this needs a proof for every instance.
Calling a guarantee tight without an instance. A guarantee $\alpha$ is tight only if some instance, or a sequence of instances, reaches $\alpha$ in the limit.
Confusing $\varepsilon$ and $\alpha$. An approximation scheme with relative error $\varepsilon$ is a $(1+\varepsilon)$-approximation algorithm for a minimization problem, but a $\frac{1}{1-\varepsilon}$-approximation algorithm for a maximization problem.
PTAS and FPTAS. The running time of a PTAS may grow like $n^{1/\varepsilon}$; only for an FPTAS it is polynomial in $\frac{1}{\varepsilon}$ as well.

34.4 In summary¶

In summary

A relative performance guarantee bounds the ratio $\mathscr{A}(I)/z(I)$ (minimization) or $z(I)/\mathscr{A}(I)$ (maximization) over all instances; an additive guarantee bounds the difference.
A guarantee is tight if it is reached by an instance, or approached by a sequence of instances; the smallest guarantee is the worst-case ratio $r(\mathscr{A})$, or the worst-case additive error $e(\mathscr{A})$.
An approximation scheme has relative error at most $\varepsilon$ for every $\varepsilon \in (0,1)$; it is a PTAS if the running time is polynomial in the size of the instance for every fixed $\varepsilon$, and an FPTAS if it is polynomial in $\frac{1}{\varepsilon}$ too.

Dashboard. A guarantee bounds the gap between a heuristic solution (a lower bound on $z(I)$ for a maximization problem, an upper bound for a minimization problem) and the optimal value, on every instance. The dashboards of the chapters of this volume collect, for the reference instances, the values of the heuristic algorithms and their guarantees; for the VCP, the MCP and the general TSP no constant guarantee exists, unless $P=NP$.

Exercises on this chapter: Principles

In the interactive lab: Tight instances.