When and where: The class meets on Tuesdays and Thursdays from 11:00 to 12:30 in room 2-146.
Instructor: Michel Goemans, room 2-351.
Office hours: I will be available on Mondays and Wednesdays (time to mutually agreed) to help prepare the presentations if need be.
This is a new undergraduate seminar in theoretical computer science. It carries CIM credit for the math department. Enrollment is limited by the department.
The topic for this Spring is on Approximation Algorithms. Approximation algorithms are efficient algorithms for NP-hard optimization problems delivering (suboptimal) solutions with a provable performance guarantee. The area has seen many developments in the last 15 years, both in terms of general techniques for their design and analysis and also with regard to inapproximability results. This seminar will cover both the foundations and also some of the latest developments.
Students will be expected to present twice during the term and also prepare typeset lecture notes of their two presentations. Preferably, the lecture notes should be typeset in LaTeX. LaTex (or TeX) is the standard way to typeset mathematics and it is a good opportunity to learn it (and once learned it makes typesetting mathematics much simpler); I can help. Here is a sample latex file and the output in ps or pdf. These sample notes use two figure files in eps format: flower.eps and evenodd.eps.
The material covered will come from chapters from the book "Approximation Algorithms" by Vijay Vazirani and also from a list of recent research papers. The exact syllabus will depend on the interest of the students participating. You'll have some control of when you speak and the topics you present. Here is a partial list of possible topics.
| Date | Student | Topic | Notes |
|---|---|---|---|
| Tu Feb 7 | - | Introduction | - |
| Th Feb 9 | Tamara | Set cover (sec. 2.1), LP (chap 12), set cover (13.1) | |
| Tu Feb 14 | Daniel | Set cover (cont'd) | |
| Th Feb 16 | Lele | Shortest superstring (sec. 2.3, 7.1) | |
| Tu Feb 21 | - | Monday schedule. No class. | - |
| Th Feb 23 | - | Class cancelled. | - |
| Tu Feb 28 | Brian | Multiway cut and k-cut (chap 4) | |
| Th Mar 2 | Adam | Multiway cut (sections 19.1, 19.2) | |
| Tu Mar 7 | Adriana | Steiner trees and Steiner forests (section 3.1 and chapter 22) | |
| Th Mar 9 | Katherine | Knapsack (chapter 8) | |
| Tu Mar 14 | M. Goemans | Maximum cut problem | - |
| Th Mar 16 | Philip | Maximum satisfiability (chapter 16) | |
| Tu Mar 21 | Nancy | Facility location (chapter 24) | |
| Minji | Max Asymmetric TSP and superstring (paper by Lewenstein and Sviridenko) | ||
| Th Mar 23 | Toby | Hardness of Approximation (chapter 29 and survey by Trevisan) | |
| Tu Mar 28 | - | Spring vacation | - |
| Th Mar 30 | - | Spring vacation | - |
| Tu Apr 4: | Daniel | Sparsest Cut (Linial, London, Rabinovich) | |
| Th Apr 6 | Minji | Parallel Machine Scheduling and Generalized Assignment | |
| Tu Apr 11 | Phil | Counting Problems (Chapter 28) | |
| Th Apr 13 | Toby | Hardness of Approximation, PCP cont'd | |
| Tu Apr 18 | - | Patriots' day. | - |
| Th Apr 20 | Lele | Sorting by reversals (Kececioglu and Sankoff, and chap 10 of Pevzner) | |
| Tu Apr 25 | Adriana | Leighton, Maggs, Rao paper on packet routing | |
| Th Apr 27 | Adam | Eucliden TSP (chap 11) | |
| Tu May 2 | Tamara | Online algorithms (chap 13 of Hochbaum) | |
| Th May 4 | Brian | Bounded-degree MST (new paper by Goemans) | |
| Tu May 9 | Mihai | Khot et al. inapproximability paper for maxcut | |
| Th May 11 | Mihai | Khot et al. inapproximability paper for maxcut | |
| Tu May 16 | Nancy | Local search for facility location | |
| Th May 18 | Katherine | Bin packing |
MIT muses' serenade on Valentine's day.
Grading policy. Your grade will be based on your participation (i.e. your own presentations, and also your participation during other presentations) and also on the quality of the lecture notes. You are expected to attend all lectures (if not excused). There will be no problem sets and no final.
The prerequisites are listed as 18.404 and 18.410. If you have not taken both, contact Michel Goemans ("lastname"@math.mit.edu) for permission.