Combinatorial algorithm finds minimum cost flows faster on dense graphs
Combinatorial Minimum Cost Flow in Almost-Linear Time on Dense Graphs
Data Structures and Algorithms
Summary
Minimum-cost flow problems involve finding the cheapest way to route stuff through a network. The authors present a new combinatorial algorithm that solves this problem faster than previous similar methods on dense networks. They introduce a technique that turns a general network into a simpler kind of network (a DAG) without losing much accuracy or speed. This helps because solving the problem on these simpler networks is easier, and their approach combines this with an existing method to get the faster overall result. This work could lead to simpler and faster algorithms for similar problems in the future.
What this means in practice
- •For network infrastructure teams: Improve routing cost optimization for high-density communication or transportation networks using faster combinatorial methods tailored to dense topologies.
- •For logistics planners: Use efficient minimum-cost flow computations to optimize transportation or delivery networks where dense connectivity is common.
Authors
Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
Abstract
We give a combinatorial algorithm that computes an exact minimum-cost flow in $n^{2+o(1)}$ time. This is the first combinatorial improvement since Goldberg-Tarjan [GT87], and is almost optimal in dense graphs. All previous faster algorithms, including the almost-linear-time algorithm of Chen et al. [CKL+22], rely on interior-point methods. Our main conceptual contribution is a black-box reduction from exact minimum-cost flow on general graphs to its approximation on DAGs, with only an $n^{o(1)}$ loss on the running time. This reduction allows future work on combinatorial minimum-cost flow to focus on DAGs, typically much easier to handle than general graphs. Our $n^{2+o(1)}$-time algorithm follows by combining this reduction with a simple augmenting-path-based approximation algorithm on DAGs. The reduction is based on a new structural result, called a flow-cost-preserving DAG projection. Given an arbitrary directed graph, this construction produces a DAG that approximately preserves both the congestion of flows and their cost up to a small loss.