Approximation Algorithms

The task of determining an optimal solution for a given problem (discrete optimization problem) is ubiquitous in computer science. A prominent example is the Travelling Salesman Problem where the goal is to find a shortest tour that visits a given set of locations. Unfortunately, for many optimization problems, no efficient algorithms are known (and under standard complexity theoretic assumptions, no such algorithms are expected to exist). However, feasible solutions are still required in practice. Thus, one approach is to determine efficient algorithms that provide provably good (but not necessarily optimal) solutions. In this lecture we discuss the design and analysis of techniques for such algorithms. Namely, we consider methods that provide a guaranteed approximation ratio (i.e., a bounded ratio between the objective value of a computed solution and the objective value of an optimal solution). For example, we will see an algorithm for the Travelling Salesman Problem where the ratio between the tour provided by the algorithm is at most two times the value of a shortest tour.

By the end of this course participants should be able to analyze simple approximation algorithms with respect to their quality. They should also be able to apply basic design techniques (e.g., greedy, local search, scaling, and LP-based methods) to approximately solve discrete optimization problems.

In this lecture we use material from the following textbooks

• "Approximation Algorithms" by V. Vazirani
• "The Design of Approximation Algorithms" by David P. Williamson and David B. Shmoys (pdf)