Negative-weight shortest paths and unit capacity minimum cost flow in O(m^10/7 W) time (extended abstract)

DOI10.1137/1.9781611974782.48zbMATH Open1410.68291arXiv1605.01717OpenAlexW4249075686MaRDI QIDQ4575786FDOQ4575786

Authors: Michael B. Cohen, Aleksander Mądry, Piotr Sankowski, Adrian Vladu 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: In this paper, we study a set of combinatorial optimization problems on weighted graphs: the shortest path problem with negative weights, the weighted perfect bipartite matching problem, the unit-capacity minimum-cost maximum flow problem and the weighted perfect bipartite $b$-matching problem under the assumption that $VertbVer{t}_1=O(m)$. We show that each one of these four problems can be solved in $ildeO(m^{10/7}logW)$ time, where $W$ is the absolute maximum weight of an edge in the graph, which gives the first in over 25 years polynomial improvement in their sparse-graph time complexity. At a high level, our algorithms build on the interior-point method-based framework developed by Madry (FOCS 2013) for solving unit-capacity maximum flow problem. We develop a refined way to analyze this framework, as well as provide new variants of the underlying preconditioning and perturbation techniques. Consequently, we are able to extend the whole interior-point method-based approach to make it applicable in the weighted graph regime.

Full work available at URL: https://arxiv.org/abs/1605.01717

Recommendations

• Minimum cost flows in graphs with unit capacities
• Minimum-cost flows in unit-capacity networks
• scientific article; zbMATH DE number 5039783
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• The exact path length problem.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Flows in graphs (05C21) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (15)

• Embedding-preserving rectangle visibility representations of nonplanar graphs
• Min-Cost Flow in Unit-Capacity Planar Graphs
• Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
• Minimum cost flow in the CONGEST model
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• Status determination by interior-point methods for convex optimization problems in domain-driven form
• Quadratically regularized optimal transport on graphs
• Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model
• Minimum-cost flows in unit-capacity networks
• Fast algorithms via dynamic-oracle matroids
• Minimum cost \(b\)-matching problems with neighborhoods
• Minimum cost flows in graphs with unit capacities
• Unit Capacity Maxflow in Almost $m^{4/3}$ Time
• Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
• Hardness results for structured linear systems

This page was built for publication: Negative-weight shortest paths and unit capacity minimum cost flow in \(\tilde{O}(m^{10/7}\log W)\) time (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575786)