Electrical Flows Primitive and Fast Graph Algorithms

on YouTube ↗01h 09m

" summary

Argues that electrical flow computed via fast Laplacian solvers becomes a basic primitive that, when wrapped in a multiplicative weights iterative scheme, yields provable speedups: approximate s–t max flow and minimum cut in near-linear (m polylog n) time, and faster routines for multicommodity and related problems. Shows the actual reduction, the solver and update steps, and runtime bounds; demonstrates the framework composes to give concrete algorithmic improvements over classic augmenting-path methods.

AI-written summary · about

" chapters (4)

1. 0:00Start
2. 17:48Path-following Interior-point method IPM
3. 34:06Connection II: Random Spanning Trees
4. 50:38Connection IV: Cover and Commute Times of Random Walks

" related talks

• 07mVertex Connectivity in Poly-logarithmic Max-flowsSorrachai Yingchareonthawornchai · 9th Annual Simons Institute Industry Day
• 17mSolving Max-Min Fair Resource Allocations Quickly on Large GraphsUmesh Krishnaswamy, Himanshu Raj, Santiago Segarra, Pooria Namyar, Behnaz Arzani, Srikanth Kandula, Daniel Crankshaw, Ramesh Govindan · 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24)
• 53mOptimal Power Flow: Relaxation, Online Algorithm, Fast DynamicsSteven Low · Real-Time Decision Making
• 01h 05mGraph Algorithms in the MPC ModelSlobodan Mitrovic · Sublinear Algorithms Boot Camp 2024
• 30mThree Goals in Parallel Graph Computations: High Performance, High Productivity, and Reduced Comm...Aydin Buluç · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 52mFine-Grained Complexity and Algorithm Design for Graph Reachability and Distance ProblemsKarl Bringmann · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 16mMinFlow: High-performance and Cost-efficient Data Passing for I/O-intensive Stateful...Tao Li, Yongkun Li, Yinlong Xu, John C. S. Lui, Wenzhe Zhu · 22nd USENIX Conference on File and Storage Technologies (FAST '24)
• 32mFrom Sparse Matrices to Graphs and Back AgainJohn Gilbert · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)