Debmalya Panigrahi

D203, LSRC

Email: debmalya@cs.duke.edu

Office Hours: By appointment (send me an email)

Teaching Assistant (TA)

Kevin Sun

D227, LSRC

Email: ksun@cs.duke.edu

Office Hours: By appointment (send me an email)

Lectures: Wednesdays and Fridays 3:05 pm - 4:20 pm in North Building 311

We will use Piazza for all discussions and course correspondence.

- 12/6/2019: The project presentations will be on Monday, 12/16 at 10 am - 12 pm in North 306.
- 12/2/2019: Prof. Panigrahi will hold an office hour today at 3 - 4 pm in his office.
- 11/23/2019: Prof. Panigrahi will hold an office hour on Monday, 11/25 at 3 - 4 pm in his office.
- 11/18/2019: The homework problems have been posted. The solutions are due on December 16 and must be submitted to the instructor by email.
- If you cannot access the Piazza page, please email the TA.

- 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

- Homework problems (no collaboration): 30% weight
- Class participation: 10% weight
- Grading a homework problem: 10% weight
- Project (in groups of 2-3): 50% weight (10% presentation, 40% outcome)

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

Network Flows | ||||||

Lecture 1 | Wed Aug 28 | Introduction and administrivia Ford-Fulkerson Maxflow-Mincut theorem |
Ford-Fulkerson paper | Notes | ||

Lecture 2 | Fri Aug 30 | LP Duality of Maxflow-Mincut Edmonds-Karp |
Edmonds-Karp paper | Notes | ||

Lecture 3 | Wed Sep 4 | Blocking Flows, Dinitz's Algorithm Push-Relabel (Goldberg-Tarjan) |
Dinitz's algorithm Goldberg-Tarjan paper |
Notes | ||

Lecture 4 | Fri Sep 6 | Maximum Multicommodity Flow Garg-Könemann |
Garg-Könemann paper | Notes | ||

Cuts and Rounding | ||||||

Lecture 5 | Wed Sep 11 | Multiway Cut, Multicut CKR Rounding |
Calinescu-Karloff-Rabani paper | Notes | ||

Lecture 6 | Fri Sep 13 | Multicut (cont.), Sparsest Cut GVY Rounding |
Garg-Vazirani-Yannakakis paper | Notes | ||

Lecture 7 | Wed Sep 18 | Sparsest Cut (cont.) | Leighton-Rao paper
Linial-London-Rabinovich paper |
Notes | ||

Global Min Cuts and Applications | ||||||

Lecture 8 | Fri Sep 20 | The Contraction Algorithm Recursive Contraction |
Karger paper (randomized contraction) Karger-Stein paper |
Notes | ||

Lecture 9 | Wed Sep 25 | Uniform Sampling for Cut Sparsification Connectivity parameters |
Karger paper (random sampling) Benczúr-Karger paper |
Notes | ||

Lecture 10 | Fri Sep 27 | Cut Sparsification via Edge Strengths | same as above | Notes | ||

Lecture 11 | Wed Oct 2 | Network Reliability | Karger paper (network reliability) Karp-Luby-Madras paper |
Notes | ||

Network Design | ||||||

Lecture 12 | Fri Oct 4 | Metric TSP, Christofides algorithm Metric Steiner Tree/Forest |
Agarwal-Klein-Ravi paper Goemans-Williamson paper (Steiner forest) |
Notes | ||

Lecture 13 | Wed Oct 9 | Primal-Dual algorithm for Steiner Forest Generalized Steiner Forest |
same as above | Notes | ||

Lecture 14 | Fri Oct 11 | Iterative Rounding for Generalized Steiner Forest |
Jain paper | Notes | ||

Lecture 15 | Wed Oct 16 | Online Steiner Tree | Imase-Waxman paper | Notes | ||

Lecture 16 | Fri Oct 18 | Online Steiner Forest | Awerbuch-Azar-Bartal paper
Berman-Coulston paper |
Notes | ||

Spectral Graph Theory | Lecture notes: Dan Spielman, Lap Chi Lau | |||||

Lecture 17 | Wed Oct 23 | Introduction and Preliminaries | see above | Notes | ||

Lecture 18 | Fri Oct 25 | Electrical Flows | see above | Notes | ||

Lecture 19 | Wed Oct 30 | Spectral Sparsification via Effective Resistances | Spielman-Srivastava paper | Notes | ||

Multiplicative Weight Update | Arora-Hazan-Kale survey | |||||

Lecture 20 | Fri Nov 1 | Weighted/Randomized Majority Algorithm | see above | Notes | ||

Lecture 21 | Wed Nov 6 | MWU for Packing LPs, Maximum Flow | Christiano-Kelner-Mądry-Spielman-Teng | Notes | ||

Semidefinite Programming | ||||||

Lecture 22 | Fri Nov 8 | Maximum Cut | Goemans-Williamson paper (maximum cut) | Notes | ||

Lecture 23 | Wed Nov 13 | Graph Coloring | Wigderson paper
Blum paper Karger-Motwani-Sudan paper |
Notes | ||

Lecture 24 | Fri Nov 15 | Sparsest Cut (cont.) | see Lectures 6-7 | Notes | ||

Lecture 25 | Wed Nov 20 | ARV algorithm for Sparsest Cut | Arora-Rao-Vazirani paper | Notes | ||

Lecture 26 | Fri Nov 22 | ARV algorithm for Sparsest Cut (cont.) | see above | see above |