Fall 2017 - COMPSCI 632 - Approximation Algorithms


Debmalya Panigrahi
D203, LSRC
Email: debmalya@cs.duke.edu

Lectures: Mondays and Wednesdays 1:25pm - 2:40pm in  LSRC D106
Office Hours: By appointment (send me an email)

We will use Piazza for all discussions and course correspondence.



This course will cover some basic concepts in approximation algorithms. This includes:


COMPSCI 532 (or an equivalent graduate course in algorithms). Talk to the instructor if you have never taken such a course but are comfortable with analytical reasoning and have taken at least one course (at any level) each in algorithms and discrete mathematics.


The course grades will be determined based on:


Course Plan

Date Contents References Remarks Scribe notes1                       Scribe
Lecture 1 Mon Aug 28 Introduction and administrivia
Why Approximation Algorithms? Intractability, inefficiency, uncertainty
Problems: Vertex cover
Techniques: Local and global methods, Sampling and estimation, Linear programs
Limits: integrality gaps, hardness of approximation
Notes Nat
Lecture 2 Wed Aug 30 Local search/Greedy: Set cover, Submodular maximizaton, Precedence constraint scheduling, List scheduling Notes Nat
Lecture 3 Mon Sep 4 Local search/Greedy: TSP, Clustering Notes Reza
Lecture 4 Wed Sep 6 Dynamic programming/Data rounding: Knapsack, Bin packing Notes Harsh
Mon Sep 11 No class. Instructor travel.
Wed Sep 13 No class. Instructor travel.
Lecture 5 Mon Sep 18 The primal-dual method: Vertex cover, Set cover, Feedback vertex set, Facility location Notes Xiang
Lecture 6 Wed Sep 20 The primal-dual method: Facility location, k-median Notes Mark
Lecture 7 Mon Sep 25 The primal dual method: k-median (cont.)
Dual fitting: Vertex cover, Set cover
Notes Brandon
Lecture 8 Wed Sep 27 Dual fitting: Facility location Notes Alex
Lecture 9 Wed Sep 27 Randomized rounding: Set cover, Congestion minimization Notes Eli
Lecture 10 Mon Oct 2 Randomized rounding: Congestion minimization (cont.), Max SAT Notes Aaron
Lecture 11 Wed Oct 4 Randomized rounding: Max SAT (cont.)
Deterministic rounding: Min cost matchings, Generalized assignment problem
Notes Kevin
Mon Oct 9 No class. Fall break.
Lecture 12 Wed Oct 11 Iterative rounding: Maximum weight matching, Minimum spanning tree Notes Hanrui
Lecture 13 Mon Oct 16 Iterative rounding: Minimum spanning tree (cont.), Degree-bounded spanning tree Notes Shweta
Lecture 14 Wed Oct 18 Iterative rounding: Degree-bounded spanning tree (cont.)
Multiway cut
Notes Abe
Lecture 15 Mon Oct 23 Multicuts, Multi-commodity flows
Semi-definite programming: Maximum cut
Notes Erin
Lecture 16 Wed Oct 25 Semi-definite programming: Maximum cut (cont.)
Integrality gaps: Vertex cover, Set cover
Dependent rounding: Group steiner tree
Notes Fred
Lecture 17 Mon Oct 30 Dependent rounding: Group steiner tree (cont.) Notes Keerti
Lecture 18 Wed Nov 1 Semi-definite programming: Graph coloring Notes Feng
Lecture 19 Mon Nov 6 Metric embeddings Notes Xingyu
Lecture 20 Wed Nov 8 Metric embeddings: Sparsest cut Notes Yuan
Lecture 21 Mon Nov 13 Metric embeddings: Sparsest cut (cont.) Notes Kangning
Lecture 22 Wed Nov 15 Semi-definite programming: Sparsest cut
Lecture 23 Mon Nov 20 Semi-definite programming: Sparsest cut (cont.)
Online algorithms: Ski-rental, Set cover
Wed Nov 22 No class. Thanksgiving recess.
Lecture 24 Mon Nov 27 Online algorithms: Set cover (cont.), Steiner tree
Lecture 25 Wed Nov 29 Hardness of approximation: PCP theorem and reductions
1 Disclaimer: The scribe notes have not been reviewed for correctness.