Theory Lunch Seminar - Ta-Wei Tu

— 1:00pm

Location:
In Person - Gates Hillman 8102

Speaker:
TA-WEI TU , Ph.D. Student, Theory Group, Computer Science Department, Stanford University
https://taweitu.github.io/

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs

In this talk, I will present a new combinatorial algorithm for maximum flow that is based on running the weighted push-relabel algorithm introduced in [BBST'24] on "shortcut" graphs. The use of shortcuts not only improves the running time from n{2+o(1) to Õ(n2) (i.e., near-linear in dense graphs), but, more importantly, also greatly simplifies both the algorithm and analysis. Our algorithm is randomized but only because of the use of standard randomized cut-matching game. Therefore, using existing alternatives, we also give a deterministic Õ(n2) time algorithm for "vertex-capacitated" max-flow. This is the first near-linear time such algorithm in any density regime. 

Based on joint work with Aaron Bernstein, Joakim Blikstad, Jason Li, and Thatchaphol Saranurak.

Event Website:
https://www.cs.cmu.edu/~theorylunch/abstractsHTML/20250507.html

Add event to Google
Add event to iCal