Computer Science 593
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.
Professor: Moses Charikar - 305 CS Building firstname.lastname@example.org
Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387 email@example.comTeaching Assistants: TBA