**Spring 2011**

**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:*

to find objects whose existence is assured by the Lovasz Local Lemma.

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.

(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 *