Many interesting discrete optimization problems are NP-hard. Thus, unless P=NP, there are no efficient algorithms to find optimal solutions to such problems. Instead we can relax the requirement of finding an optimal solution, and try to find a solution that approximates the value of the optimal solution. The goal of this course is to gain insight into the key algorithmic techniques used to design and analyze approximation algorithms.

• Prove correctness of approximation algorithms
• Design approximation algorithms for a given problem
• Independently read scientific papers, and describe the contents in a comprehensive manner
• Analyze, evaluate, and compare quality of solutions to problems.
• Apply and extend advanced techniques--e.g. LP-duality, randomized and deterministic rounding, local search, lower bounding techniques --to NP-hard problems to obtain an approximation algorithm
• Show hardness of approximation for a given problem.

Advanced state-of-the-art techniques for designing approximation algorithms, especially for NP-complete problems. Topics includes clustering, LP-duality, LP-rounding, greedy algorithms, local search, tree metrics, primal-dual method.

Design of Approximation Algorithms" by Shmoys and Williamson

This course is for students with a research interest in algorithms.

The course will consist of weekly meetings, where the text book and solutions to exercises are discussed among the participants. There are no traditional lectures.