What is an Approximation Algorithm?

When we are faced with a combinatorial optimization problem, our goal is to design an algorithm that satisfies three important properties. However, when we deal with an NP-hard problem, it is not at all clear whether such algorithms that satisfy all three aforementioned properties even exist. So, one natural approach to slightly simplify our lives is to relax one of the three properties. In the case of approximation algorithms, we decide to relax property (2). This means that we are interested in efficient algorithms that always return feasible solutions, and what we care to bound is the gap between the value of the solution they return and the value of an optimal solution.