Approximation Algorithm

algorithms

Definition

Approximation Algorithm

An approximation algorithm is an polynomial time algorithm that aims to approximate the optimal solution of a hard problem.

A minimising approximation algorithm $A$ is called $\epsilon$-approximation algorithm, for $e\ge 1$, if:

$$\forall x\in X:\frac{c_A(x)}{c_{opt}(x)}\le \epsilon$$

A maximising approximation algorithm $A$ is called $\epsilon$-approximation algorithm, for $0\le \epsilon \le 1$, if:

$$\forall x\in X:\frac{c_A(x)}{c_{opt}(x)}\ge \epsilon$$

where $X$ is the set of problem instances, $c_A(x)$ is the approx. algorithm’s, $c_A(x)>0$ is the actual solution value, and $c_{opt}(x)>0$ is the optimal solution value. The value $\epsilon$ is called the performance guarantee.