Theory Lunch Seminar - Ta-Wei Tu May 7, 2025 12:00pm — 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
