4 papers · 1 filter
Deterministic Padded Decompositions and Negative-Weight Shortest Paths
Jason Li
We obtain the first near-linear time deterministic algorithm for negative-weight single-source shortest paths on integer-weighted graphs. Our main ingredient is a deterministic con…
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 $…
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…
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 $…