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.

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

- 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

- 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%)

Date | Contents | References | Remarks | Scribe notes^{1} |
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 ^{2} n) stretch, O(log n loglog n) stretchFakcharoenphol-Rao-Talwar paper |
|||

Tues Apr 21 | Project presentations |