Factor-Delta Approximation Algorithm

computation

Definition

Factor- $\delta$ Approximation Algorithm

Let $\Pi$ be a minimisation or maximisation problem, and let $\delta :{\mathbb{N}}^{+}\to {\mathbb{Q}}^{+}$.

Minimisation

$$f_{\Pi }(I,S)\le \delta (|I|)\cdot \mathrm{OPT}(I)$$

where $\delta \ge 1$.

Maximisation

$$f_{\Pi }(I,S)\ge \delta (|I|)\cdot \mathrm{OPT}(I)$$

where $\delta \le 1$.

An algorithm $\mathcal{A}$ is a factor-$\delta$ approximation algorithm for $\Pi$ if, on each instance $I$, $\mathcal{A}$ produces a factor-$\delta$ approximate solution for $I$ and runs in polynomial time in $|I|$.

Solution

Definition

Factor- $\delta$ Approximate Solution

A feasible solution $S$ to an instance $I$ is a factor-$\delta$ approximate solution if it satisfies the approximation bound below.

Link to original

NP-Hard Optimisation Problem

Definition

$\delta$-Approximable NP-Hard Optimisation Problem

An NP-hard optimisation problem $\Pi$ is called $\delta$-approximable if it admits a factor-delta approximation algorithm

Link to original