18.434 Seminar in Theoretical Computer Science

Spring 2010

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.