Many well-known optimization problems are hard to solve, meaning that the existence of a polynomial-time algorithm for solving them would imply that P = NP. Approximation algorithms are a possible way to reasonably deal with hard optimization problems. The goal of such algorithms is to efficiently produce feasible solutions that are close, in some sense, to an optimal solution for the problem. Such algorithms can be thought of as heuristics that have a performance guarantee in terms of the quality of the solution produced. We will present an introduction to the study of approximation algorithms, starting from simple examples, and gradually covering different techniques used in the area. In the process of presenting such techniques, we will address a variety of optimization problems such as scheduling, clustering, and satisfiability. The first half of the tutorial will be easily followed by anyone with a background on algorithms, and with basic notions of complexity theory. The second half will present techniques that involve linear programming and/or probabilistic strategies.

The slides are available.