Continuous Approaches to Network Flows

• All participants should be familiar with the introduction to electrical flows in Chapter 8 in the book Network Flow Algorithms by David P. Williamson
• For an introduction to interior point methods, we refer to the article A still simpler way of introducing the interior-point method for linear programming be Mehlhorn and Saxena.

1. Daitch, Spielman: Faster Approximate Lossy Generalized Flow via Interior Point Algorithms,
   STOC'08 https://dl.acm.org/doi/pdf/10.1145/1374376.1374441, https://arxiv.org/pdf/0803.0988.pdf
2. Kelner, Orecchia, Sidford, Zhu: A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time,
   https://arxiv.org/abs/1301.6628, 2013
3. Madry: Computing Maximum Flow with Augmenting Electrical Flows,
   https://arxiv.org/abs/1608.06016v1, 2016
4. Kathuria, Liu, Sidford: Unit Capacity Maxflow in Almost O(m^(4/3) ) Time
   FOCS 2020 (merge of two papers)
5. Gao, Liu, Peng 2021:Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao
   https://arxiv.org/abs/2101.07233, 2021 (two talks)
6. Axiotis, Madry, Vladu: Faster Sparse Minimum Cost Flow by Electrical Flow Localization,
   https://arxiv.org/abs/2111.10368v1, 2021 (two talks)
7. Brand, Gao, Jambulapati, Lee, Liu, Peng, Sidford: Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers
   https://arxiv.org/abs/2112.00722v1, 2021 (three talks)
8. Li, Panigrahi: Deterministic Min-cut in Poly-logarithmic Max-flows,
   https://arxiv.org/abs/2111.02008, 2021

• A regular participation in the talks and an active collaboration are mandatory for passing the seminar.
• The talks will take approximately 75 minutes. The remaining 15 minutes are intended for a discussion.
• Each participant has to write a summary consisting of one or two pages.
• Each participant has to give an approval talk (typically three weeks before the regular talk). Passing the approval talk is a prerequisite for giving the regular seminar talk.