Fall 2017 - COMPSCI 632 - Approximation Algorithms

Administration

Instructor
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.

Announcements

08/28: Please sign up as a student of this course on Piazza. If you have not received the invitation yet, please email the instructor.
08/28: Please sign up for scribing on the Google spreadsheet.
09/25: It is now admissible to work in groups of two on the homework. Please mention your partner's name when writing the solutions. Also, make sure that you write the solution on your own and are able to explain everything that you wrote.

Synopsis

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

Combinatorial techniques: dynamic programming; local search; local ratio; primal-dual
Relaxation and rounding: threshold rounding; randomized rounding; pipage rounding; iterative rounding; semi-definite programs; integrality gap
Approximation primitives: distance preservers; sparsifiers; metric embeddings
Hardness of approximation: gap creating/preserving reductions, introduction to PCP

Prerequisites

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.

Grading

The course grades will be determined based on:

Homework (about 10 problems, in groups of 1-2). (30% weight)
Problems will be added throughout the semester: HW problems
Course project (in groups of 2-3). (50% weight)
Class participation. This includes scribing 1-2 lectures. (20% weight)
Scribing Templates: tex, ref, pdf

References

[WS] The Design of Approximation Algorithms. David P. Williamson and David B. Shmoys. Cambridge University Press.
[V] Approximation Algorithms. Vijay V. Vazirani. Springer.

Course Plan

	Date	Contents	References	Remarks	Scribe notes¹	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

¹ Disclaimer: The scribe notes have not been reviewed for correctness.