Approximation Algorithm

3 credits

We study design and analysis techniques for approximation algorithms, i.e., efficient algorithms that provide solutions to combinatorial optimization problems with mathematically provable guarantees on the ratio of their objective values to that of the optimal solution. Examples of techniques include linear programming, dynamic programming, local search, and greedy algorithms.