Debmalya Panigrahi

D203, LSRC

Email: debmalya@cs.duke.edu

Lectures: Mondays and Wednesdays 3:05pm- 4:20pm in French Science 2237

Office Hours: By appointment (send me an email)

We will use Piazza for all discussions and course correspondence.

- 01/11: Please sign up as a student of this course on Piazza. If you have not received the invitation yet, please email the instructor.

- 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). (30% weight)

Homework Problems - Course project (in groups of 2-3). (40% weight)
- Scribing (due the day after lecture). (20% weight)

Templates: tex, ref, pdf - Class participation. (10% weight)

Date | Contents | References | Remarks | Scribe notes^{1} |
Scribe | |

Network Flows | ||||||

Lecture 1 | Wed Jan 11 | Introduction and administrivia Ford-Fulkerson Maxflow-Mincut theorem |
Ford-Fulkerson paper Edmonds-Karp paper |
|||

Mon Jan 16 | No class. Martin Luther King, Jr. Holiday. | |||||

Wed Jan 18 | Instructor travel. Lecture rescheduled. | |||||

Lecture 2 | Mon Jan 23 | Blocking Flows (Dinitz) | Dinitz's algorithm | |||

Lecture 3 | Wed Jan 25 | Blocking Flows (contd.) Capacity Scaling Beyond flow decomposition (Goldberg-Rao) |
Goldberg-Rao paper | |||

Lecture 4 | Mon Jan 30 | Beyond flow decomposition (contd.) Preflows |
||||

Lecture 5 | Wed Feb 1 | Push-Relabel (Goldberg-Tarjan) | Goldberg-Tarjan paper | |||

Global Mincuts | ||||||

Lecture 6 | Mon Feb 6 | The contraction algorithm (Karger) Uniform sampling theorem (Karger) |
Contraction algorithm Uniform sampling |
Notes | ||

Lecture 7 | Wed Feb 8 | Connectivity parameters | Notes | |||

Lecture 8 | Mon Feb 13 | Cut sparsification via connectivity sampling (Fung-Hariharan-Harvey-Panigrahi) |
Fung-Hariharan-Harvey-Panigrahi paper Benczur-Karger paper |
Notes | ||

Lecture 9 | Wed Feb 15 | Deterministic contraction (Nagamochi-Ibaraki) | Nagamochi-Ibaraki paper (unit capacity) Nagamochi-Ibaraki paper (capacitated) |
Notes | ||

Lecture 10 | Mon Feb 20 | 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 | ||

Back to Flows | Notes | |||||

Lecture 11 | Wed Feb 22 | Randomized maxflow algorithm (Karger-Levine) | Karger-Levine paper | Notes | ||

Lecture 12 | Mon Feb 27 | Introduction to Spectral Graph Theory | Lecture notes: Dan Spielman, Lap Chi Lau | Notes | ||

Lecture 13 | Wed Mar 1 | Electrical Flows | Same as above | Notes | ||

Lecture 14 | Wed Mar 8 | Maximum Flows using Electrical Flows | Christiano et al. paper | Notes | ||

Mon Mar 13 | Spring break | |||||

Wed Mar 15 | Spring break | |||||

Network Design | ||||||

Lecture 15 | Mon Mar 20 | Minimium Spanning Tree | Karger-Klein-Tarjan paper | Notes | ||

Lecture 16, 17, 18 (Extended makeup lecture) |
? | 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 |
||

Lecture 19 | Wed Mar 22 | Node-weighted Steiner tree/forest (Klein-Ravi) | Klein-Ravi paper | Notes | ||

Lecture 20, 21 (Extended makeup lecture) |
? | 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 |
||

Lecture 22 | Mon Mar 27 | Generalized Steiner Forest: primal dual algorithms | Williamson-Goemans-Mihail-Vazirani paper Goemans et al. paper |
Notes | ||

Lecture 23 | Wed Mar 29 | Generalized Steiner Forest: iterative rounding | Jain's paper | Notes | ||

Lecture 24 | Mon Apr 3 | Maximum cut: SDP relaxation (Goemans-Williamson) |
Goemans-Williamson paper | Notes | ||

Lecture 25 | Wed Apr 5 | Group Steiner tree (Garg-Konjevod-Ravi) | Garg-Konjevod-Ravi paper | Notes | ||

Lecture 26 | Mon Apr 10 | Metric embeddings | Bartal's papers: O(log ^{2} n) stretch, O(log n loglog n) stretchFakcharoenphol-Rao-Talwar paper |
|||

Wed Apr 12 | ||||||

Mon Apr 17 | ||||||

Wed Apr 19 | Project presentations |