Fall 2020: Approximation Algorithms and Hardness of Approximation

Approximation algorithms have been actively studied in both algorithms and complexity theory, culminating in optimal approximation algorithms for some fundamental problems; they achieve some approximation guarantees and no polynomial time algorithm can do better under some complexity conjectures. The theory of approximation algorithms also leads to beautiful connections between algorithms, complexity, and some areas of mathematics. This course will provide an overview of these connections, stressing techniques and tools required to prove both algorithms and complexity results.