Approximation Algorithm

computation approximation

Definition

Approximation Algorithm

An approximation algorithm is a polynomial-time algorithm for an optimisation problem that returns a feasible solution whose objective value is guaranteed to be close to the value of an optimal solution.

The guarantee is measured by an approximation ratio.

Guarantee

Let $I$ be an instance of an optimisation problem. Let $C_A(I)$ be the objective value returned by an algorithm $A$, and let $C_{\mathrm{OPT}}(I)$ be the optimum value.

Minimisation

For a minimisation problem, a $\rho$-approximation algorithm satisfies

$$C_A(I)\le \rho \cdot C_{\mathrm{OPT}}(I)$$

for every instance $I$, where $\rho \ge 1$.

Smaller $\rho$ is better. The ideal value is $\rho =1$.

Maximisation

For a maximisation problem, an $\alpha$-approximation algorithm satisfies

$$C_A(I)\ge \alpha \cdot C_{\mathrm{OPT}}(I)$$

for every instance $I$, where $0<\alpha \le 1$.

Larger $\alpha$ is better. The ideal value is $\alpha =1$.

An approximation algorithm is therefore stronger than a heuristic. A heuristic may return good solutions on many instances, but it has no required worst-case guarantee.

Proof idea

The optimum value is usually unknown. The proof must compare the algorithm’s value with a bound on the optimum.

Minimisation

For minimisation, one proves a lower bound $L(I)$ on the optimum:

$$L(I)\le C_{\mathrm{OPT}}(I).$$

If the algorithm’s solution also satisfies

$$C_A(I)\le \rho \cdot L(I),$$

then

$$C_A(I)\le \rho \cdot C_{\mathrm{OPT}}(I).$$

Maximisation

For maximisation, one proves an upper bound $U(I)$ on the optimum:

$$C_{\mathrm{OPT}}(I)\le U(I).$$

If the algorithm’s solution also satisfies

$$C_A(I)\ge \alpha \cdot U(I),$$

then

$$C_A(I)\ge \alpha \cdot C_{\mathrm{OPT}}(I).$$

This is the main difficulty: the algorithm must be analysed against an optimum that it does not compute.

Use

Approximation algorithms are mainly used for NP-hard optimisation problems. They keep polynomial running time and arbitrary inputs, but give up exact optimality.

This is different from restricting the input class or using an exact algorithm with exponential running time.

Examples

Vertex cover

In minimum vertex cover, a maximal matching gives a simple $2$-approximation.

Let $M$ be a maximal matching. Every vertex cover must contain at least one endpoint of each edge in $M$. Since the edges in $M$ are disjoint,

$$|M|\le C_{\mathrm{OPT}}(I).$$

The algorithm returns both endpoints of each matched edge, so

$$C_A(I)=2|M|\le 2\cdot C_{\mathrm{OPT}}(I).$$

Thus, the algorithm is a $2$-approximation.

MaxSAT

In maximum satisfiability, a maximisation guarantee has the opposite direction.

If an algorithm returns an assignment satisfying at least $\frac{3}{4}$ as many clauses as an optimal assignment, then

$$C_A(I)\ge \frac{3}{4}\cdot C_{\mathrm{OPT}}(I).$$

Thus, it is a $\frac{3}{4}$-approximation under the maximisation convention.