Approximation Ratio

computation approximation

Definition

Approximation Ratio

An approximation ratio measures the worst-case distance between the value returned by an approximation algorithm and the value of an optimal solution.

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

Minimisation minimisation problem, a $\rho$-approximation guarantee means

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

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

Maximisation maximisation problem, an $\alpha$-approximation guarantee means

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

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

$${\rho }_A(I)=\max \left\{\frac{C_A(I)}{C_{\mathrm{OPT}}(I)},\frac{C_{\mathrm{OPT}}(I)}{C_A(I)}\right\}.$$

Then $A$ has approximation ratio $\rho (n)$ if, for every instance $I$ of size $n$,

$${\rho }_A(I)\le \rho (n).$$

Direction

The direction of the guarantee depends on the optimisation problem.

Minimisation

For minimisation, smaller values are better.

Thus, $\rho =2$ means that the returned value is at most twice the optimum.

Maximisation

For maximisation, larger values are better.

Thus, $\alpha =\frac{3}{4}$ means that the returned value is at least three quarters of the optimum.

Under the symmetric convention, this corresponds to ratio $\frac{4}{3}$.

Meaning

An approximation ratio is a worst-case statement. It does not say that the algorithm is usually close to optimum. It says that every valid instance is bounded by the stated factor.

The optimum value is usually not known while the algorithm runs. The proof therefore compares the algorithm’s value with a lower or upper bound on the optimum.

Examples

Vertex cover

A $2$-approximation for minimum vertex cover returns a vertex cover whose size is at most twice the optimum:

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

This is a minimisation guarantee.

MaxSAT

A $\frac{3}{4}$-approximation for maximum satisfiability returns an assignment satisfying at least three quarters as many clauses as an optimal assignment:

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

Under the symmetric convention, this is ratio $\frac{4}{3}$.