Interesting discrete optimization problems are everywhere, from classic operations research problems, such as scheduling, facility location, and traveling salesman problems, to computer science problems in internet routing, data mining, social network analysis and advertising. Yet most interesting discrete optimization problems are NP-hard. Thus unless P = NP, there are no efficient algorithms to find optimal solutions to such problems. This course shows how to design approximation algorithms: efficient algorithms that find provably near-optimal solutions.
The course is organized around central techniques for designing approximation algorithms. Every couple of weeks, a new technique will be introduced and illustrated through several applications, covering greedy, local search, linear and semidefinite programming relaxations, (randomized) rounding, metric embedding and sampling.
