Approximation Algorithms

An introduction to approximation algorithms: when a problem is NP-hard and the exact optimum is out of computational reach, settle for a polynomial-time solution with a proof that it is within a guaranteed factor of optimal. The approximation ratio, the trick of bounding an unknowable optimum by a computable lower bound, the spectrum from constant factors to PTAS and FPTAS, the hardness-of-approximation limits, and how the approximation ratio is the offline cousin of the competitive ratio.