CSCI 2510 - Approximation Algorithms - Fall 2008

CSCI 2510 - Approximation Algorithms

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.

Midterm, final

Midterm: oral exam in my office. 20 minutes. I ask you about class material (until Oct 15 lecture), you tell me about it using the whiteboard. Can be scheduled at any time between Oct 20 and Oct 30. Send me email to set a date.
Final: same, scheduled between Dec 5 and Dec 10. Program: all lectures from Oct 20 to Dec 3.
Final Schedule: Monday: Olya (9am), Yuri (10am), Justin (3:40). Tuesday: Cody (9am), Fabio (9:40), Feng-Hao (10:20), Diana (11:20), Dan (1), Shay (2), Sarah M. (2:30), Serdar (2:50), Sarah E. (3:10), Eric (4), Sam (4:30).

Homework

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.
Due date Exercises (one among:)
9/10 2pm
1.1, 1.3, 1.7, 2.2, 2.11, 1.4.
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
6.2, 12.1,12.8,12.9,12.11
10/10 3pm
either this, or one simplex exercise from this. IP models: see here or here; simplex: see this, this, and that.
10/17 3pm
no homework due
10/24 3pm
14.4, 14.6, 14.3, 14.5, 13.7
10/31 3pm
16.5, 16.8, 16.2, 16.5, 16.4, 14.1, 16.6, 16.1,
11/7 3pm
18.1, 18.3, 18.5, 18.8, 18.9,
11/14,3pm
20.7, 22.2, 22.6, 22.8
Tuesday 11/25 3pm
21.3, 21.6, 22.4, greedy
11/28
no homework due
12/5 3pm
26.8, 26.12, 26.13, 26.14

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
Ellipsoid method

Oct 20
Set cover via dual fitting and via primal-dual
ch. 13 and 15
Oct 22
Set cover via randomized rounding
ch. 14
Oct 27
Exercises: students present

Oct 29
Max Sat, derandomizing
ch. 16
Nov 3
Multicut on trees
ch. 18
Nov 5
Guest lecture: Euclidean TSP approximation scheme (Aparna Das)
ch. 11
Nov 10
Multicut in general graphs
ch. 20
Nov 12
Steiner forest via primal-dual
ch. 22, notes
Nov 17
Online bipartite matching
paper
Nov 19
Online bipartite matching
ch. 21
Nov 24
Online auctions
notes
Nov 26
Day before Thanksgiving: no class

Dec 1
Online auctions and online weighted paging

Dec 3
Semi-definite programming
ch. 26
Dec 8
Hardness of Approximation
ch. 29
Dec 10
No class