CS 7520 - Approximation Algorithms

Spring 2008

[ Lectures] [Homework]


Description

Efficient approximation algorithms for computationally hard problems. Combinatorial algorithms and mathematical programming methods. Hardness of approximation.

Lectures

Tue-Thu 9:30-11:00, Klauss 1447.
The material covered in each lecture together with references and/or notes will be posted in the Lectures web page.

Instructor

Milena Mihail, Associate Professor
Office phone: 404-385-0617
Cell Phone: 404 379-1460
Office hours: Tue 1:00-3:00, Klaus 2138, or by appointment. mihail@cc.gatech.edu

All email concerning this course should have a subject entitled CS 7520.

Teaching Assistant

Varun Kanade, email varunk@cc.gatech.edu

Text and Notes

(1) Approximation Algorithms, Vijay Vazirani.
(2) Notes from a similar class.

Grading

Weekly or biweekly homeworks 30%.
You may collaborate or read any resource you want in solving the problems, but please indicate your collaboration group and/or the resources you used. You MUST write your answers by yourselves, without any collaboration and without using any resource, as if you are taking a test.

A 30min-1hour (possibly group) classroom presentation, on a topic related to approximation algorithms, jointly decided by yourselves and the instructor 10%. Topics will be decided together with the instructor , or you may propose your own (research or interest related) topic. The purpose of this project is to make sure that you can read and understand the main points of some paper(s) related to the class, but not presented in the lectures.

Class participation 10%. In particular, no A will be given to a student that has unexcused absences in more than 25% of the lectures.

Take home midterm, 20%.

Take home final, 30%.

Web Announcements

You are responsible for reading these announcements at the end of the day, every Tuesday and Thursday.

Tue Jan 8: Homework 1 is now posted and due in two weeks (Tue Jan 22nd).

Thu Jan 31: Homework 2 is now posted and due Feb 12.

Tue Feb 26: Homework 3 is now posted and due March 6.

Thu Feb 28: There is a slightly corrected (and simpler) version of Homework 3.

Thu Feb 28: Make sure you see the notes and other material posted for reading for the Dual Fitting method (Lectures of 2-19 and 2-26), in the lectures page.

Thu March 6: Homework 4 is now posted and due March 13. Please send me email if you have trouble accessing the page.

Thu March 6: The takehome midterm exam will be the week after spring break. The exam will be posted Tue March 25 (and will be emailed to all students just in case the web page is not working properly), and will be due Thu March 27 (you can email it to me, or slide it under my door, say before midnight... or any time... as long as I have it in the morning of Fri March 28). The material for the midterm is all that has been covered in the class upto (including) March 13, and Homeworks 1-4.

Mon March 24: The midterm exam is now posted and due Tuesday April 1st. Please send me email if you have trouble accessing the page. Please also send me email if you have any questions about the exam. Take your time and read before you answer the questions. There will be no lectures this week Tue March 25 and Thu March 27.

Mon April 21: The reading list is now posted. We will discuss these readings in class on Tuesday April 22nd. Please send email to the instructor if you have any questions, or if you want to report on a topic/problem outside the proposed list. I will be available for office hours by appointment any time in the next couple of weeks. Please submit your report by Friday May 2 (grades are due by noon Monday May 5).

Thu April 24: The final exam is now posted. It is due Friday May 2 (grades are due by noon Monday May 5). For the final exam you may use references, but you should mention which references you have used. You must work alone, no collaboration.

Web Site

Class Web-site http://www.cc.gatech.edu/~mihail/index7520.html.

This site is maintained by Milena Mihail, please report problems to mihail@cc.gatech.edu.