Analysis and design of algorithms - chapter 8: Approximation Algorithms

Many problems of practical significance are NP-complete but are too important to abandon merely because obtaining an optimal solution is intractable.
If a problem is NP-complete, we are unlikely to find a polynomial time algorithm for solving it exactly, but it may still be possible to find near-optimal solution in polynomial time.
In practice, near-optimality is often good enough.
An algorithm that returns near-optimal solutions is called an approximation algorithm.