Monday |
10:00-10:50 am |
Tuesday |
2:00-2:50 pm |
Friday |
10:00-10:50 am |
Lectures: 9:30-10:50am in CS 213
Office Hours: TBA
Text:
Approximation Algorithms,
by Vijay V. Vazirani,
Springer-Verlag, 2001.
Another useful book is Approximation Algorithms for NP-Hard Problems
edited by Dorit S. Hochbaum.
Overview:
A great deal of research has addressed the issue
of finding algorithms for optimization problems that, while not necessarily
giving the true optimum, satisfy some guaranteed error bound.
Some of the motivation for this has come from the development of
the theory of NP-completeness, which gave convincing evidence that
for many optimization problems there does not exist an efficient
algorithm that always gives the true optimum.
In this course we will discuss some of the approximation
results that have been achieved, and methods that have been used to
achieve them.
I plan to cover only a subset of the topics in the text, including
I also plan to discuss two topics from outside the text:
Because this is a small seminar, I may adjust the topics to be covered
as the quarter progresses.
Coursework:
There will be several homeworks throughout the quarter, which will be
the major factor in determining students' grades. Students will
also be encouraged to consider giving a presentation of some paper
to the class.
Students may elect to take the course either for a grade or on
a S/U basis.
Homework:
Note:
Generally I want you to work alone on the starred
problems. You may consult with other people or look up the solution
in a journal, but then you must report this on your homework and will
receive less credit. (The first homework has no starred problems.)
For the unstarred problems, feel free to work with
other students as you wish, but please write the solution
you turn in yourself, and be sure you understand it yourself.
Various approximation results
Techniques for building approximation algorithms, including
dynamic programming and linear programming
(including the primal-dual approach)
Some inapproximability results based on the PCP Theorem
The work of Grötschel, Lovász, and Schrijver relating
optimization and separation problems
Total unimodularity (we won't apply this to approximation algorithms,
but for some integer programming problems
it gives a way of showing that the linear programming relaxation
has the same solution value)
| Homework 1 | Homework 2 | Homework 3 |
Some useful links:
Material on total unimodularity, and some of the material on linear programming, is drawn from Chapters 2 and 8 of A Course in Combinatorial Optimization by Alexander Schrijver
Lecture notes on Approximation Algorithms by Michel X. Goemans
A catalog of approximation results edited by Pierluigi Crescenzi and Viggo Kann