Spring 2020 — Convex Optimization and Maximum Flows

Location: See update

Time: Round table discussions each Monday at 6:30 pm, and presentations each Friday at 6:00 pm

Logistics: Please join our emailing list here to stay up to date with current events. Fill out this Google Form for course units.

Files: scribe note template

Update on 3/13/2020 - due to recent developments regarding the transmission of COVID-19, we will be moving our meetings to an online video conferencing service. More details regarding how you can connect will be available soon. Please stay safe and wash your hands!

In the past decade, major advancements in the design and analysis of algorithms have risen from a confluence of techniques developed in continuous and discrete optimization. One example in which this blend of approaches has been particularly effective is towards algorithms for solving maximum flow problems on graphs. This semester, we will read recent papers related to maxflow and learn about techniques developed in optimization related to analyzing Laplacian linear system solvers, interior point methods, and preconditioner construction.

Paper List

A selection of papers that we may read

Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
- Paul Christiano, Jonathan A. Kelner, Aleksander Mądry, Daniel A. Spielman, and Shang-Hua Teng
A simple combinatorial algorithm for solving SDD systems in nearly-linear time
- Jonathan A. Kelner, Aaron Sidford, Lorenzo Orecchia, and Zeyuan Allen Zhu
Navigating central path with electrical flows: from flows to matchings, and back
- Aleksander Mądry
Path finding methods for linear programming: Solving linear programs in \(\mathcal{O}(\sqrt{\text{rank}})\) iterations and faster algorithms for maximum flows
- Yin Tat Lee and Aaron Sidford
An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
- Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford
Computing maximum flows with augmenting electrical flows
- Aleksander Mądry
Generalized preconditioning and network flow problems
- Jonah Sherman
Flows in almost linear time via adaptive preconditioning
- Rasmus Kyng, Richard Peng, Sushant Sachdeva, Di Wang
Faster energy maximization for faster maximum flows
- Yang P. Liu and Aaron Sidford

Additional Resources

A number of talks regarding the above papers have been recorded and posted to YouTube
- Aleksander Mądry’s talk on approximating maxflow using electrical flows
- Aleksander Mądry’s introduction to interior point methods
- Aleksander Mądry’s talk on solving maxflow using interior point methods
- Aaron Sidford’s talk on solving linear programs in \(\mathcal{O}(\sqrt{\text{rank}})\) iterations
Bootcamp from the Simon’s Institute’s Fall 2014 program on Algorithmic Spectral Graph Theory
Bootcamp from the Simons Institute’s Fall 2017 program on Bridging Continuous and Discrete Optimization

Date	Topic	Resources
2/3/2020	Reading group General meeting and preliminary logistics — Soda 380 @ 7:00pm Discuss semester long goals, plans for weekly meetings, and unit requirements.
2/7/2020	[CKMST11] Part 1 presented by Antares — Soda 373 @ 6:00pm Read § 3 of Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs Round table discussion in Soda 373 @ Wednesday 2/5 7:00pm will cover experts, electrical flows, and a sketch of the \(\tilde{\mathcal{O}}(\frac{m^{3/2}}{\epsilon^{5/2}})\) time algorithm.	Scribe notes coming soon
2/14/2020	[CKMST11] Part 2 presented by Albert and Natalie — Soda 373 @ 6:00pm Read § 4 of Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs Round table discussion in Cory 212 @ Monday 2/10 6:30pm will sketch the \(\widetilde{\mathcal{O}}(\frac{m^{4/3}}{\epsilon^3})\) time algorithm.	Scribe notes coming soon
2/21/2020	Maxflow noting and coding workday — Soda 373 @ 6:00pm No round table discussion this week; we’ll be coding and writing scribe notes for CKMST on Friday.
2/28/2020	[KOSZ13] Part 1 presented by Josh and Naveen — Soda 373 @ 6:00pm Read § 2-4 and 6 of A simple, combinatorial, algorithm for solving SDD systems in nearly-linear time Round table discussion in Cory 212 @ Monday 2/24 6:30pm will sketch the \(\widetilde{\mathcal{O}}(m \log^2 n \log \log n \log (\frac{n}{\epsilon}))\) time algorithm for solving SDD linear systems.	Scribe notes coming soon
3/6/2020	[KOSZ13] Part 2 presented by Robert — Soda 373 @ 6:00pm Read § 6, 9, 10 of A simple, combinatorial, algorithm for solving SDD systems in nearly-linear time Round table discussion in Cory 212 @ Monday 3/2 6:30pm will sketch the geometric intuition for the KOSZ algorithm.	Scribe notes coming soon
3/13/2020	Campus Recommendation to Move to Online Meetings due to COVID-19 — no meeting Please stay safe and wash your hands!
3/19/2020	[Sherman13] presented by Prof. Rao — Zoom @ 4:00pm Thursday 3/19 Read Nearly Maximum Flows in Nearly Linear Time Link to the webcast will be available before the meeting.