Min-cost flow solver made simpler and faster using distance oracles
A Simpler and Faster Min-Cost Flow Solver via Min-Ratio Cycles from Distance Oracles
Data Structures and Algorithms
Summary
Finding the cheapest way to send flow through a network is a tricky problem that previous work turned into smaller subproblems involving ratios of costs and distances. Earlier approaches used complex data setups to solve these subproblems. The authors show that these can be solved more simply and quickly by directly using a dynamic data tool called a distance oracle. This discovery not only streamlines the process but also speeds up solving minimum cost flow problems and can handle graphs that change over time.
What this means in practice
- •For network engineers: Optimize data routing with faster and simpler minimum cost flow computations in changing network topologies.
- •For logistics planners: Improve routing and shipment cost solutions by efficiently handling incremental updates in transport networks.
Authors
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg, Aurelio Sulser
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.