CSCI 2510 - Approximation Algorithms

CS 251: When, where, who

Instructor: Claire Mathieu (claire at cs.brown.edu), CIT 555, x36066
Lecture Location and Time: CIT 506, MW 2:00 - 3:20 pm
Office hours: Fr. 10-12 and by appointment.
Prerequisites: CS157 or equivalent. This is a good course for senior undergraduates who have enjoyed CS 157 and want to go beyond that, and for graduate students who want a Theory course.
Bibliography:
Approximation Algorithms, Vijay V. Vazirani, Springer-Verlag Berlin Heidelberg. I have the 2001 edition; there is a later edition. Vazirani said: "It is only the second reprinting, not second edition. I corrected many errors. I might have added a couple of exercises; not a significant difference."

What

How does one deal with NP-hard problems? For optimization problems, one possibility is to attempt to find, in polynomial time, a solution which is guaranteed to have value relatively close to optimal. This is the approach taken in the design of approximation algorithms.

This graduate course focuses on the design and analysis of polynomial time approximation algorithms with proven performance guarantees for NP-hard optimization problems. The goal is to understand techniques and algorithmic paradigms which have wide applicability. Much of the course revolves around techniques based on linear programmming. This year the course will be structured around reading Vazirani's textbook. We will alternate meetings where Claire will go over some selected chapters, and meetings where we will discuss and present solutions to exercises from the textbook.

After the course: we will be comfortable with the design of approximation algorithms for graph problems, and with linear programming as a technique for approximation algorithms. We will have had an introduction to semidefinite programming as a technique for approximation algorithms, and to the hardness of approximation. We will have a nice set of solutions to some exercises from the textbook.

How

Solve exercises from Vazirani's textbook (each writes up one per week), present them in class, write up textbook-quality solutions and post them on course web page. It is recommended that you work together in groups of 2 or 3 but your writeup must be individual. You are encouraged to work on more than one exercise, however you must write up and turn in one and only one exercise. For the writeup, the organization and the reasoning should be clear, ideally textbook quality: not just a correct solution, but the simplest and most elegant possible. For presentation, you will probably make your life easier if you use Latex but it's up to you. See here for help on Latex. Chapter 1 of Vazirani's textbook is available here. or here.

Due date	Exercises (one among:)
9/10 2pm	1.1, 1.3, 1.7, 2.2, 2.11.
9/19 3pm	class problem, 3.1, 3.2, 3.3,4.2,4.3,4.7
9/26 3pm	class problem,5.1,5.3 (version 1), 5.3 (version 2),5.4
10/3 3pm	ch. 6 and 12
10/10 3pm	choopse one simplex exercise from among end of chapter of this.
10/17 3pm	ch. 13
10/24 3pm	ch. 14 and 15
10/31 3pm	ch. 16

2008 Schedule

Date	Topic	Book chapter
Sept 5	Vertex cover, max bipartite matching Konig's theorem.	ch. 1
Sept 8	Greedy set cover	sec. 2.1
Sept 10	Shortest superstring, and Exercises: students present.	sec. 2.3
Sept 15	Steiner trees, Max flow min cut	sec. 3.1
Sept 17	Cuts, Gomory-Hu trees	ch. 4
Sept 22	Microsoft opening: no class
Sept 24	k-center, dominating sets	ch. 5
Sept 29	Feedback vertex set, cycle space of a graph	ch. 6
Oct 1	Linear programming duality	ch. 12
Oct 6	Max flow min cut by duality, Simplex algorithm,
Oct 8	Exercises: students present
Oct 13	Columbus day: no class
Oct 15	Set cover via dual fitting	ch. 13
Oct 20	Set cover via randomized rounding	ch. 14
Oct 22	Set cover via primal-dual	ch. 15
Oct 27	Exercises: students present
Oct 29	Max Sat, derandomizing	ch. 16
Nov 3
Nov 5
Nov 10
Nov 12
Nov 17
Nov 19
Nov 24
Nov 26	Day before Thanksgiving: no class
Dec 1
Dec 3
Dec 8	(Reading period): there will be class
Dec 10?	Reading period: no class?