Lecturer


Sayan Bhattachaya and Parinya Chalermsook


Time 
Monday 1618, first meeting 14 October, 2013

Syllabus

PDF

Announcements 

(NEW) The note for Lecture 9 has been posted.
 (NEW) The solution for Homework 3 has been posted.
 A note for lecture 8 is up! This note contains a bit more than what I actually taught though.
 Assignment 3 is posted!!! Warning: It's a long assignment!
 Solutions for Homework 1 and 2 have been posted!!!
 A supplementary note for lecture 6 is up!
 Slides for Lecture 5 are up!
 Problem set 2 is up!!! Due 9 December in class.
 The note for lecture 3 is up!
 The first problem set is posted. Due 18 November (in class)!
 If you take this course for credit, please send me (Parinya) an email with your name ASAP.

Room 
024 in the MPI building (E1 4)

Prerequisites 
Basic knowledge of discrete mathematics and algorithms.

Content

The course intends to cover some standard techniques, applied to central problems, in approximation algorithms. Here is the list of tentative topics.
 Basic Combinatorial Techniques
 LP Rounding: Routing Problems, Flow and Cut Problems, Network Design Problems
 Metric and Cuts
 PrimalDual Method: Steiner Network and Cut Problems

Preliminary
Schedule

No. 
Date

Lecturer 
Topic

Content

Supplementary Notes

0 
14 October

Sayan

Introduction



1 
21 October

Sayan

Set Cover

Chapter 1


2 
28 October 
Sayan

Set Cover (cont.) 
Chapter 1


3 
4 November 
Parinya

Combinatorial Techniques: Greedy 
WS 2.2, 2.3, 8.1 and Edge Disjoint Paths (see the note)

Lecture 3

4 
11 November 
Parinya

Combinatorial Techniques: Local Search, DP 
WS 2.6, 3.1 and Max Cut Local Search


5 
18 November 
Parinya

DP (cont) and LP Rounding 
WS 3.2, 3.3, and 4.1 
Lecture 5 
6 
25 November 
Parinya

LP Rounding (cont) 
WS 4.2, 4.3, 5.1, 5.2, and 5.3

Lecture 6

7 
2 December 
Parinya

LP Rounding (cont) 
WS 4.5, 5.8, 

8 
9 December 
Parinya

Chernoff Bounds and Randomized LP Rounding 
WS 5.10, 5.11, 6.1, and 6.2

Lecture 8 
9 
16 December 
Parinya

Metric method and Multicut 
See the note

Lecture 9

10 
6 January 
Sayan

PrimalDual Method 
Chapter 7


11 
13 January 
Sayan

PrimalDual Method 
Chapter 7


12 
20 January 
Sayan

Local Search 
Chapter 9 

13 
27 January 
Sayan

Recap 









Grading 
The grades are based on homework and a final exam.
 The final exam will be held on February 17
 You have to get at least 50% of the homework for the
admission to the final exam.

Homework 
There will be 4 problem sets. Each problem set has 25 questions.
 Problem Set 1 [pdf]  Solution: [pdf]
( Due: 18 November, 2013 )
 Problem Set 2 [pdf]  Solution: [pdf]
( Due: 9 December, 2013 )
 Problem Set 3 [pdf]  Solution: [pdf]
( Due: 13 January, 2014 )
 Problem Set 4 [pdf]
( Due: 27 January, 2014 )

Main References 
 A book by Shmoys and Wiliamson (link)
