Editing Approximation algorithm (section)

== Structure of approximation algorithms ==
Given an optimization problem:

<math>\Pi: I \times S</math>

where <math>\Pi</math> is an approximation problem, <math>I</math> the set of inputs and <math>S</math> the set of solutions, we can define the cost function:

<math>c: S \rightarrow \mathbb{R}^+</math>

and the set of feasible solutions:

<math>\forall i \in I, S(i) = {s \in S: i\Pi_s}</math>

finding the best solution <math>s^*</math> for a maximization or a minimization problem:

<math>s^* \in S(i)</math>, <math>c(s^*) = min/max \ c(S(i))</math>

Given a feasible solution <math>s \in S(i)</math>, with <math>s \neq s^*</math>, we would want a guarantee of the quality of the solution, which is a performance to be guaranteed (approximation factor).

Specifically, having <math>A_{\Pi}(i) \in S_i</math>, the algorithm has an '''approximation factor''' (or '''approximation ratio''') of <math>\rho(n)</math> if <math>\forall i \in I \ s.t. |i| = n</math>, we have:

* for a ''minimization'' problem: <math>\frac{c(A_{\Pi}(i))}{c(s^*(i))}\leq\rho(n)</math>, which in turn means the solution taken by the algorithm divided by the optimal solution achieves a ratio of <math>\rho(n)</math>;
* for a ''maximization'' problem: <math>\frac{c(s^*(i))}{c(A_{\Pi}(i))}\leq\rho(n)</math>, which in turn means the optimal solution divided by the solution taken by the algorithm achieves a ratio of <math>\rho(n)</math>;

The approximation can be proven ''tight'' (''tight approximation'') by demonstrating that there exist instances where the algorithm performs at the approximation limit, indicating the tightness of the bound. In this case, it's enough to construct an input instance designed to force the algorithm into a worst-case scenario.