Approximation Algorithms

Undergraduate

Many problems arising in computer science are NP-hard and therefore we do not expect efficient algorithms for solving them exactly. This has led to the study of approximation algorithms where algorithms are supposed to run fast but can return approximate solutions. This course provides a broad overview of the main techniques involved in designing and analyzing such algorithms. It also explores connections between algorithms and mathematical fields such as algebra, geometry, and probability.