Spring 2015 - COMPSCI 590.01 - Advanced Topics in Computer Science: Graph Algorithms

Administration

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

Lectures: Tuesdays and Thursdays 11:45am- 1pm in LSRC D106
Office Hours: By appointment (send me an email)

We will use Piazza for all discussions and course correspondence.

Announcements

03/22: New homework problems added.
03/18: New homework problems added.
02/11: New homework problems added.
01/29: Please submit the one-page project proposal by tomorrow, Friday 01/30.
01/29: Homework problems and scribing templates have been uploaded.
01/08: Please sign up as a student of this course on Piazza. If you have not received the invitation yet, send me an email.

Synopsis

This course is intended to be an advanced course in theoretical computer science covering some of the most influential work in graph algorithms over the last two decades. The current installment will focus on graph connectivity. This includes:

Flows: Augmenting paths; blocking flows; push-relabel; scaling; randomization; electrical flows and spectral techniques
Cuts: Duality with flows; Gomory-Hu trees; graph smoothing; global min-cut algorithms: randomized contractions, cut and spectral sparsification
Network Design: Steiner trees: LP formulations and iterative rounding; Steiner forests: primal dual; metric embeddings; group Steiner rounding; iterative rounding for SNDP; node-weighted and directed Steiner tree; online network design algorithms

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:

6 out of 10-15 problems given through the course of the semester (due one week after last lecture, no collaboration). (weightage: 30%)
Homework Problems
Course project (in groups of 2-3). (weightage: 50%)
Scribing (one lecture per student, due the day after lecture). (weightage: 10%)
Templates: tex, ref, pdf
Class participation. (weightage: 10%)

Course Plan

	Date	Contents	References	Remarks	Scribe notes¹	Scribe
		Network Flows
Lecture 1	Thurs Jan 8	Introduction and administrivia Ford-Fulkerson Maxflow-Mincut theorem	Ford-Fulkerson paper Edmonds-Karp paper
Lecture 2	Tues Jan 13	Blocking Flows (Dinitz)	Dinitz's algorithm
Lecture 3	Thurs Jan 15	Blocking Flows (contd.) Capacity Scaling Beyond flow decomposition (Goldberg-Rao)	Goldberg-Rao paper
Lecture 4	Tues Jan 20	Beyond flow decomposition (contd.) Preflows
Lecture 5	Thurs Jan 22	Push-Relabel (Goldberg-Tarjan)	Goldberg-Tarjan paper
		Global Mincuts
Lecture 6	Tues Jan 27	The contraction algorithm (Karger) Uniform sampling theorem (Karger)	Contraction algorithm Uniform sampling		Notes	Yuhao
Lecture 7	Thurs Jan 29	Connectivity parameters			Notes	Jiangwei
Lecture 8	Tues Feb 3	Cut sparsification via connectivity sampling (Fung-Hariharan-Harvey-Panigrahi)	Fung-Hariharan-Harvey-Panigrahi paper Benczur-Karger paper		Notes	Allen
Lecture 9	Thurs Feb 5	Deterministic contraction (Nagamochi-Ibaraki)	Nagamochi-Ibaraki paper (unit capacity) Nagamochi-Ibaraki paper (capacitated)		Notes	Janardhan
Lecture 10	Tues Feb 10	Recursive contraction (Karger-Stein) Near-linear time min-cut algorithm (Karger)	Karger-Stein paper Karger's near-linear time algorithm Gabow's min-cut algorithm		Notes	Brandon
		Back to Flows			Notes
Lecture 11	Thurs Feb 12	Randomized maxflow algorithm (Karger-Levine)	Karger-Levine paper		Notes	Nadi
	Tues Feb 17	School closed due to snow
Lecture 12	Thurs Feb 19	Introduction to Spectral Graph Theory	Lecture notes: Dan Spielman, Lap Chi Lau		Notes	Yan
Lecture 13	Tues Feb 24	Electrical Flows	Same as above		Notes	Stavros
	Thurs Feb 26	School closed due to snow
	Tues Mar 3	Cancelled due to instructor travel
Lecture 14	Thurs Mar 5	Maximum Flows using Electrical Flows	Christiano et al. paper		Notes	Abhishek
	Tues Mar 10	Spring break
	Thurs Mar 12	Spring break
		Network Design
Lecture 15	Tues Mar 17	Minimium Spanning Tree	Karger-Klein-Tarjan paper		Notes	Allen
	Thurs Mar 19	Cancelled due to departmental event
Lecture 16, 17, 18 (Extended makeup lecture)	Sun Mar 22	Steiner tree: approximation via MST Steiner forest: primal dual algorithm (Agarwal-Klein-Ravi, Goemans-Williamson) Online Steiner tree (Imase-Waxman) Online Steiner forest (Awerbuch-Azar-Bartal, Berman-Coulston)	Agarwal-Klein-Ravi paper Goemans-Williamson paper Imase-Waxman paper Awerbuch-Azar-Bartal paper Berman-Coulston paper		Notes Notes	Yuhao, Nat
Lecture 19	Tues Mar 24	Node-weighted Steiner tree/forest (Klein-Ravi)	Klein-Ravi paper		Notes	Xiangyu
Lecture 20, 21 (Extended makeup lecture)	Wed Mar 25	Online set cover and non-metric facility location (Alon-Awerbuch-Azar-Buchbinder-Naor) Online Node-weighted Steiner tree (Naor-Panigrahi-Singh)	Alon et al. paper (online set cover) Alon et al. paper (online network design) Naor-Panigrahi-Singh paper Liaghat-Hajiaghayi-Panigrahi paper		Notes Notes	Abhinandan, Rupert
Lecture 22	Thurs Mar 26	Generalized Steiner Forest: primal dual algorithms	Williamson-Goemans-Mihail-Vazirani paper Goemans et al. paper		Notes	Sam
Lecture 23	Tues Mar 31	Generalized Steiner Forest: iterative rounding	Jain's paper		Notes	Brandon
	Thurs Apr 2	Cancelled due to instructor travel
Lecture 24	Tues Apr 7	Maximum cut: SDP relaxation (Goemans-Williamson)	Goemans-Williamson paper		Notes	Xi
Lecture 25	Thurs Apr 9	Group Steiner tree (Garg-Konjevod-Ravi)	Garg-Konjevod-Ravi paper		Notes	Ios
Lecture 26	Tues Apr 14	Metric embeddings	Bartal's papers: O(log² n) stretch, O(log n loglog n) stretch Fakcharoenphol-Rao-Talwar paper
	Tues Apr 21	Project presentations

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