2021/11/19 by Kyriakos Axiotis, Aleksander Mądry, Axiotis, Kyriakos +3 · 2 citations
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Smart Parking Systems Research
paper · doi:10.48550/arxiv.2111.10368
openalex publication_date 2021/11/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give an \widetildeO(m3/2 - 1/762 log (U+W)) time algorithm for minimum cost flow with capacities bounded by U and costs bounded by W. For sparse graphs with general capacities, this is the first algorithm to improve over the \widetildeO(m3/2 logO(1) (U+W)) running time obtained by an appropriate instantiation of an interior point method [Daitch-Spielman, 2008]. Our approach is extending the framework put forth in [Gao-Liu-Peng, 2021] for computing the maximum flow in graphs with large capacities and, in particular, demonstrates how to reduce the problem of computing an electrical flow with general demands to the same problem on a sublinear-sized set of vertices -- even if the demand is supported on the entire graph. Along the way, we develop new machinery to assess the importance of the graph's edges at each phase of the interior point method optimization process. This capability relies on establishing a new connections between the electrical flows arising inside that optimization process and vertex distances in the corresponding effective resistance metric.