CS 7520 - Approximation Algorithms

Spring 2011

[ Lectures] [Homework]


Description
Combinatorial, problem specific approximation algorithms. Greedy, layering, recursive, dynamic programming methods.
Integer Programs, Linear Programs and LP-duality.
Rounding, dual fitting, primal-dual schema and lagrangians in the design of approximation algorithms.
Smoothed Analysis.
Semidefinite programming and its applications in the design of approximation algorithms.
Approximate Counting.
Spectral Methods and approximbility.
Elements of Quantum Computation.
Hardness of Approximation.
All the above, with variations in online, dynamic, parallel, distributed, stateless contexts, as suitable.

Lectures
Tue-Thu 12:05-1:30, Klaus 2456.
The material covered in each lecture together with references and/or notes, as suitable, will be posted in the Lectures web page.

Instructor
Milena Mihail, Associate Professor
Office: 404-385-0617 (answering machine unstable)
Cell: four zero four - three seven nine - one four six zero
Office hours: Tue 10-12, Fri 10-12, Klaus 2138, or by appointment.
Email: lastname at cc dot gatech dot edu
All email concerning this course should have a subject entitled CS 7520.

Texts and Notes
(1) Approximation Algorithms, Vijay Vazirani.
(2) The Design of Approximation Algorithms, David Williamson and David Shmoys.
You may download the PDF file from Williamson's page, until the book goes to press.
(3) Papers on topics not covered in the book and notes from similar classes will be posted on the corresponding lectures.
(4) Algorithm Design, Jon Kleinberg and Eva Tardos (optional).

Grading
(1) Weekly 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.
(2) A 30min-1hour (possibly group) classroom presentation, on a special topic in 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 technical material related to the class.
(3) Class participation 10%. In particular, no A will be given to a student that has unexcused absences in more than 25% of the lectures.
(4) Two midterms, 30% (open book, open notes, no collaboration).
THE 1st MIDTERM IS THU FEB 24 (TAKE HOME). Class drop date is March 4.
(5) Final exam, 20% (open book, open notes, no collaboration).

Web Announcements
You are responsible for reading these announcements at the end of the day, every Tuesday and Thursday.
Tue Jan 18: Start reading chapters 1 and 2 of Vazirani's Approximation Algorithms.
Thu Jan 20: (1) Check the Lectures page.
(2) Homework 1 is out and due Thu Jan 27.
Tue Feb 1: Homework 2 is out and due Tue Feb 8.
Thu Feb 17: (1) Check updated Lectures page.
(2) Homework 3 is out and due Thu Feb 22.
(3) The Design of Approximation Algorithms by David Williamson and David Shmoys is a new textbook.
You may download the PDF file from Williamson's page, until the book goes to press.
(4) MARK YOUR CALENDAR: Fri, 03/11/2011 at 3:05pm, Skiles 006, ACO Colloquim
TITLE: Two Needles from Exponential Haystacks
SPEAKER: Joel Spencer, Professor, Courant Institute of Mathematical Sciences, NYU
ABSTRACT: Erdos Magic proves the existence of an object but where is it?
When the random object has only exponentially small chance of working this is especially challenging. The last years have seen two great successes:

Lovasz! Moser, followed by Tardos and now Szegedy, have given an amazingly simple algorithm (the proof of correctness is not so simple!)
to find objects whose existence is assured by the Lovasz Local Lemma.

Six Suffice! Many years ago this speaker showed that n sets on n points could be two colored so that all discrepancies were at most 6\sqrt{n}
and long conjectured that no algorithm was possible. Wrong! Bansal, using semidefinite programming
in a very nice extension of Goemans-Williamson ideas, finds the coloring.


Tue March 1: (1) Check the Lectures page.
(2) Midterm 1 is now posted and due Friday March 4, NOON.
(3) There will be extra office hours Thu March 3, 9-11 in the morning.

Web Site
Class Web-site http://www.cc.gatech.edu/~mihail/index7520_11.html.
This site is maintained by Milena Mihail.
Please report problems to lastname at cc dot gatech dot edu