|
Lecturer
|
|
Sayan Bhattachaya and Parinya Chalermsook
|
|
|
Time |
Monday 16-18, 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 e-mail 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
- Primal-Dual 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
|
Primal-Dual Method |
Chapter 7
|
|
|
11 |
13 January |
Sayan
|
Primal-Dual 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 2-5 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)
|
