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

DOI10.1137/1.9781611974782.48MaRDI QIDQ4575786zbMATHOpenAlexFDO

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)

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

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)

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.

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.

Cited in

(15)

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

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)