- Series
- ACO Student Seminar
- Time
- Friday, November 12, 2021 - 1:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 314
- Speaker
- Li Chen – Georgia Tech CS – lichen@gatech.edu – https://lic225.github.io/
- Organizer
- Abhishek Dhawan
We design an O~(m)-time randomized algorithm for the l2-norm flow diffusion problem, a recently proposed diffusion model based on network flow with demonstrated graph clustering related applications both in theory and in practice. Examples include finding locally-biased low conductance cuts. Using a known connection between the optimal dual solution of the flow diffusion problem and the local cut structure, our algorithm gives an alternative approach for finding such cuts in nearly linear time.
From a technical point of view, our algorithm contributes a novel way of dealing with inequality constraints in graph optimization problems. It adapts the high-level algorithmic framework of nearly linear time Laplacian system solvers, but requires several new tools: vertex elimination under constraints, a new family of graph ultra-sparsifiers, and accelerated proximal gradient methods with inexact proximal mapping computation.
Joint work with Richard Peng and Di Wang.