Welcome to Approximation Algorithms homepage
Course DescriptionThe field of approximation algorithms developed in order to cope with NP-hardness. It provides provable guarantees on the performance of heuristics for hard problems. The course will present general techniques (such as linear programming-based approaches, local search, randomness and metric methods) that underly these algorithms.
Tentative ScopeThe first part of the course will cover traditional approximation algorithms, with combinatorial and linear programming techniques, cut problems and metric embeddings. The latter half of the course will cover topics which are related to approximation – hashing and load balancing, online algorithms, streaming, dimensionality reduction.
Among the techniques for the construction of approximation algorithms we will touch upon the following: greedy algorithms, local search, randomized methods, LP techniques, primal-dual method, semi-definite programming, metric methods.
Problems: Set cover and Vertex cover. k-center. Scheduling. TSP. Facility location. Steiner tree and other network design problems. Max-Cut and Max-SAT. Sparsest cut, multicut and other partitioning problems. Graph coloring.
Homework and GradingThere will be up to 4 written homework assignments - for a total of 40%.
There will be a final exam (or home exam) for 50%.
The remainder 10% will be based on class work and general impression.
TextbooksThe Design of Approximation Algorithms, David P. Williamson and David B. Shmoys
Approximation Algorithms, Vijay Vazirani
Algorithm Design, Jon Kleinberg and Eva Tardos
Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan