Electrical Engineering and Computer Science
menu MENU

Fall 2020: Approximation Algorithms and Hardness of Approximation

Fall 2020: Approximation Algorithms and Hardness of Approximation

Course No:
EECS 598-010
Instructor:
Euiwoong Lee
Prerequisites:
EECS 376 and 477

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.

More info (pdf)