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 be an instance of an optimisation problem. Let be the objective value returned by an algorithm , and let be the optimum value.

Minimisation

For a minimisation problem, a -approximation algorithm satisfies

for every instance , where .

Smaller is better. The ideal value is .

Maximisation

For a maximisation problem, an -approximation algorithm satisfies

for every instance , where .

Larger is better. The ideal value is .

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 on the optimum:

If the algorithm’s solution also satisfies

then

Maximisation

For maximisation, one proves an upper bound on the optimum:

If the algorithm’s solution also satisfies

then

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 -approximation.

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

The algorithm returns both endpoints of each matched edge, so

Thus, the algorithm is a -approximation.

MaxSAT

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

If an algorithm returns an assignment satisfying at least as many clauses as an optimal assignment, then

Thus, it is a -approximation under the maximisation convention.