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