When and where: MWF 1-2PM in 2-131.
Instructor: Michel Goemans, room 2-351.
This is an undergraduate seminar in theoretical computer science. It carries CIM credit for the math department. As with all CIM subjects, the emphasis is on communication, both oral and written. 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.
Textbook. The material covered will come from chapters from a forthcoming book by David P. Williamson and David B. Shmoys titled The Design of Approximation Algorithms. A copy of the book should be purchased from CopyTech.
Students will be expected to present three times during the term. The goal of the presentations is to communicate effectively the material to the other students in the class. There will also be a term paper due (in latex), on a related topic. Possible topics. A draft of the paper will be due on Fri April 2nd, with the final version due on Fri April 30th. There will be occasionally a homework exercise assigned.
Grading policy. Your grade will be based on your presentations, your participation in class (during other presentations), on the term paper, and on the solutions of the exercises assigned.
Exercises Exercise 1 (due on 3/3/2010) is here.
Schedule:
date | presenter | topic |
---|---|---|
Wed Feb 3 | Introduction | |
Fri Feb 5 | Viktor | 1.2 + 1.3 |
Mon Feb 8 | Shaunak | 1.4 + 1.5 |
Wed Feb 10 | Olga | 1.6 |
Fri Feb 12 | Michael | 1.7 |
Tue Feb 16 | Joseph | 2.1 + 2.3 |
Wed Feb 17 | Rachel | 2.4 |
Fri Feb 19 | NO CLASS. | |
Mon Feb 22 | David | 3.2 |
Wed Feb 24 | Tom | 2.5 |
Fri Feb 26 | Daniel | 2.7 |
Mon Mar 1 | No class | |
Wed Mar 3 | Jeff | 5.1-5.6 |
Fri Mar 5 | Jeff (cont'd) | |
Mon Mar 8 | Jieyun | 5.10 + 5.11 |
Wed Mar 10 | Jieyun | |
Fri Mar 12 | Joseph | 3.3 + 4.6 |
Mon Mar 15 | Joseph (cont'd) | |
Wed Mar 17 | Olga | 6.1-6.2 |
Fri Mar 19 | Olga | 6.3 |
Mon Mar 29 | David | 4.5 + 5.8 |
Wed Mar 31 | David (cont'd) | |
Fri Apr 2 | Rachel | 8.1+8.2 |
Mon Apr 5 | Rachel (cont'd) | |
Wed Apr 7 | Michael | 10.1 |
Fri Apr 9 | NO CLASS | |
Mon Apr 12 | Michael | |
Wed Apr 14 | Daniel | 7.1-7.2 |
Fri Apr 16 | Daniel | 7.3 |
Mon Apr 19 | Patriot's day | |
Wed Apr 21 | Viktor | 7.4 |
Fri Apr 23 | Viktor | 7.4 (cont'd) |
Mon Apr 26 | Tom | submodular+matroid constraint |
Wed Apr 28 | Tom | |
Fri Apr 30 | Jieyun | Bounded-degree MST |
Mon May 3 | Jieyun | |
Wed May 5 | Shaunak | PCP |
Fri May 7 | Shaunak | PCP |
Mon May 10 | no class | |
Wed May 12 | Jeff | PCP - Inapproximability |
Possible sections to be covered
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.