Contents (hide)

Welcome to Approximation Algorithms homepage

Course Description

The 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 Scope

The 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 Grading

There 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.

Textbooks

The 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

Office Hours

Thursday 14-16, room 215, building 37