Decoration
max planck institut
informatik
mpii logo Minerva of the Max Planck Society

Topics in Approximation Algorithms (Winter 2013/14)


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)
Search MPII (type ? for help)