arXiv preprint ·
A Simpler and Faster Min-Cost Flow Solver via Min-Ratio Cycles from Distance Oracles
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
The first almost-linear time maximum and minimum cost flow algorithm of Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022), reduced these flow objectives to a sequence of min-ratio cycle problems. Solving this core primitive requires approximately minimizing the ratio of a linear gradient term and an undirected length term. In Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022) and the subsequent work of Chen-Kyng-Liu-Meierhans-Probst Gutenberg (STOC 2024), intricate data structures were given to solve the min-ratio problem. We show that such a cycle can be extracted directly from the dynamic distance oracle of Kyng-Meierhans-Probst Gutenberg (STOC 2024) using linearity. This simplifies previous algorithms that relied on multiple additional steps to extract the cycle, and can be seen as evidence that solving the min-ratio cycle problem really is all about distances. As a result, we obtain a faster primal maxflow and min-cost flow solver that also extends to incremental graphs.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
The Inverse Lyndon Array
High-Dimensional Ultra-Log-Concave Distributions
An Arboricity-Sensitive Algorithm for the $K_r-e$-Free Graph Sandwich Problem
Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata
Single-Pass Estimation of the Clustering Coefficient Distribution in Graph Streams
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.