3 papers
cs.DS2025
Local Sherman's Algorithm for Multi-commodity Flow
Jason Li, Thatchaphol Saranurak
We give the first local algorithm for computing multi-commodity flow and apply it to obtain a -approximate algorithm for computing a -commodity flow on an expander with $…
cs.DS2024
Space Complexity of Minimum Cut Problems in Single-Pass Streams
Matthew Ding, Alexandro Garces, Jason Li +4
We consider the problem of finding a minimum cut of a weighted graph presented as a single-pass stream. While graph sparsification in streams has been intensively studied, the spec…
cs.DS2024
A Simple and Fast Algorithm for Fair Cuts
Jason Li, Owen Li
We present a simple and faster algorithm for computing fair cuts on undirected graphs, a concept introduced in recent work of Li et al. (SODA 2023). Informally, for any parameter $…