Following the Path of Least Resistance : An Õ(m sqrt(n)) Algorithm for the Minimum Cost Flow Problem

Yin Tat Lee, Aaron SidfordarXiv 2013 · arXiv · OpenReview

Abstract

In this paper we present an $\tilde{O}(m\sqrt{n}\log^{O(1)}U)$ time algorithm for solving the maximum flow problem on directed graphs with $m$ edges, $n$ vertices, and capacity ratio $U$. This improves upon the previous fastest running time of $O(m\min\left(n^{2/3},m^{1/2}\right)\log\left(n^{2}/m\right)\log U)$ achieved over 15 years ago by Goldberg and Rao. In the special case of solving dense directed unit capacity graphs our algorithm improves upon the previous fastest running times of of $O(\min\{m^{3/2},mn^{^{2/3}}\})$ achieved by Even and Tarjan and Karzanov over 35 years ago and of $\tilde{O}(m^{10/7})$ achieved recently by M\k{a}dry. We achieve these results through the development and application of a new general interior point method that we believe is of independent interest. The number of iterations required by this algorithm is better than that predicted by analyzing the best self-concordant barrier of the feasible region. By applying this method to the linear programming formulations of maximum flow, minimum cost flow, and lossy generalized minimum cost flow and applying analysis by Daitch and Spielman we achieve running time of $\tilde{O}(m\sqrt{n}\log^{O(1)}(U/\epsilon))$ for these problems as well. Furthermore, our algorithm is parallelizable and using a recent nearly linear time work polylogarithmic depth Laplacian system solver of Spielman and Peng we achieve a $\tilde{O}(\sqrt{n}\log^{O(1)}(U/\epsilon))$ depth algorithm and $\tilde{O}(m\sqrt{n}\log^{O(1)}(U/\epsilon))$ work algorithm for solving these problems.

Introduction

The Minimum Cost Flow (MCF) problem and the Maximum Flow problem are foundational pillars of combinatorial optimization. Given a directed graph with $n$ vertices and $m$ edges, these problems seek the most efficient way to route "flow" through a network subject to capacity constraints. Despite their ubiquity in fields ranging from logistics to computer vision, theoretical progress on general graph algorithms had largely stalled for over fifteen years.

The primary bottleneck in previous approaches, particularly those using Interior Point Methods (IPMs), was a theoretical limit on the number of iterations. Standard IPMs typically require $O(\sqrt{m})$ iterations, where $m$ is the number of constraints (edges). In dense graphs, this leads to significant computational overhead. This work by Lee and Sidford breaks this long-standing barrier, reducing the iteration complexity to $\tilde{O}(\sqrt{n})$.

Historical Context and Breakthrough

The following table illustrates the progression of algorithmic efficiency for the Minimum Cost Flow problem over the last several decades. The result presented in this paper represents the first significant improvement for general graphs since the work of Goldberg and Rao in 1998.

Comparison of running times for Minimum Cost Flow algorithms over time.

Methodology: Rethinking Interior Point Methods

The core of this breakthrough is a novel Interior Point Method that departs from traditional self-concordant barrier analysis.

Breaking the Self-Concordance Barrier

Standard IPMs follow a "central path" through the feasible region. The speed of convergence is usually tied to the self-concordance of the barrier function, which traditionally scales with the number of edges, $m$. Lee and Sidford demonstrate that by carefully weighting the barrier function, the complexity can instead be tied to the number of vertices, $n$.

The Mixed Norm and Dynamic Re-weighting

To achieve $\tilde{O}(\sqrt{n})$ iterations, the authors introduce a mixed norm to measure centrality. This norm combines the $\ell_\infty$ norm with a weighted $\ell_2$ norm, allowing the algorithm to navigate the "box" constraints of edge capacities more effectively.

Furthermore, the algorithm maintains dynamic weights on the edges based on "effective resistance." By alternating between solving electrical flow problems and updating these weights, the algorithm ensures that no single edge becomes a bottleneck, maintaining a steady progress rate proportional to $\sqrt{n}$.

Leveraging Laplacian Solvers

To ensure each iteration is computationally efficient, the method utilizes nearly linear-time Laplacian system solvers. These solvers allow the required linear systems to be processed in $\tilde{O}(m)$ time, resulting in a total work complexity of $\tilde{O}(m\sqrt{n})$.

Key Results

The primary contribution is a new complexity bound for Max Flow and Min-Cost Flow: $\tilde{O}(m\sqrt{n} \log^{O(1)} U)$.

For dense graphs, this is a transformative result. For instance, in a graph where $m = n^2$, the previous best bound was $O(n^{8/3})$. This new algorithm achieves $\tilde{O}(n^{2.5})$, marking the first improvement for dense directed graphs in 35 years. Additionally, the approach extends to "lossy" generalized minimum cost flows and is highly parallelizable, achieving polylogarithmic depth.

Discussion and Future Directions

While this result is a major theoretical milestone, several challenges remain for practical implementation. The algorithm is "weakly polynomial," meaning its runtime depends on the capacity ratio $U$. Furthermore, the constants hidden within the polylogarithmic factors are likely large, which may affect performance on real-world datasets compared to existing heuristics.

Future research may focus on simplifying these techniques to improve practical performance or pursuing the "holy grail" of flow algorithms: a nearly linear time $\tilde{O}(m)$ algorithm for general graphs.

Summary updated

Abstract

In this paper we present an $\tilde{O}(m\sqrt{n}\log^{O(1)}U)$ time algorithm for solving the maximum flow problem on directed graphs with $m$ edges, $n$ vertices, and capacity ratio $U$. This improves upon the previous fastest running time of $O(m\min\left(n^{2/3},m^{1/2}\right)\log\left(n^{2}/m\right)\log U)$ achieved over 15 years ago by Goldberg and Rao. In the special case of solving dense directed unit capacity graphs our algorithm improves upon the previous fastest running times of of $O(\min\{m^{3/2},mn^{^{2/3}}\})$ achieved by Even and Tarjan and Karzanov over 35 years ago and of $\tilde{O}(m^{10/7})$ achieved recently by M\k{a}dry. We achieve these results through the development and application of a new general interior point method that we believe is of independent interest. The number of iterations required by this algorithm is better than that predicted by analyzing the best self-concordant barrier of the feasible region. By applying this method to the linear programming formulations of maximum flow, minimum cost flow, and lossy generalized minimum cost flow and applying analysis by Daitch and Spielman we achieve running time of $\tilde{O}(m\sqrt{n}\log^{O(1)}(U/\epsilon))$ for these problems as well. Furthermore, our algorithm is parallelizable and using a recent nearly linear time work polylogarithmic depth Laplacian system solver of Spielman and Peng we achieve a $\tilde{O}(\sqrt{n}\log^{O(1)}(U/\epsilon))$ depth algorithm and $\tilde{O}(m\sqrt{n}\log^{O(1)}(U/\epsilon))$ work algorithm for solving these problems.
BibTeX
@misc{lee2013following,
  author = {Yin Tat Lee and Aaron Sidford},
  title = {{Following the Path of Least Resistance : An Õ(m sqrt(n)) Algorithm for the Minimum Cost Flow Problem}},
  year = {2013},
  eprint = {1312.6713},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1312.6713},
}
Figure