Princeton University Computer Science Department

Computer Science 593 Advanced Topics in Theory of Algorithms Approximation Algorithms Moses Charikar

Fall 2001

Course Description

This seminar course explores approximation algorithms, where the goal is to find provably good approximate solutions for optimization problems that are hard to solve exactly. Over the last several years, a number of techniques have emerged for the design of approximation algorithms for a wide variety of problems. The goal of the course is to introduce students to these general algorithmic techniques. We will try to build up to the point where students can engage in research on open problems in this area.

Mathematical programming relaxations are a very useful tool for the design of approximation algorithms. We will study approximation algorithms derived from linear programming relaxations via randomized rounding, iterative rounding, the primal dual method, lagrangean relaxation, as well as semidefinite programming based approximation algorithms. We will also examine approximations derived from greedy algorithms, local search, dynamic programming, random sampling and metric embeddings.

Classes will consist of a combination of lectures and student presentations of recent research papers.

This advanced seminar is for graduate students and advanced undergraduates who wish to pursue research in theoretical computer science. I will assume a basic knowledge of linear programming (a brief introduction will be given initially), and some previous exposure to algorithms and graph theory.
Note: Undergraduates who wish to enroll in this seminar should contact me by e-mail or in person.

Administrative Information

Lectures: M 3:05-4:55 , Room: CS 302

Professor: Moses Charikar - 305 CS Building moses@cs.princeton.edu

Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387 mml@cs.princeton.edu