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

DOI10.1137/1.9781611974782.48MaRDI QIDQ4575786zbMATH OpenOpenAlexFDO

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

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

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

(24)

• Minimum-cost flows in unit-capacity networks
• Embedding-preserving rectangle visibility representations of nonplanar graphs
• Minimum cost b-matching problems with neighborhoods
• Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
• Status determination by interior-point methods for convex optimization problems in domain-driven form
• Minimum cost flows in graphs with unit capacities
• Quadratically regularized optimal transport on graphs
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
• Unit Capacity Maxflow in Almost $m^{4/3}$ Time
• Min-Cost Flow in Unit-Capacity Planar Graphs
• Hardness results for structured linear systems
• Minimum cost flow in the CONGEST model
• Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model
• Fast algorithms via dynamic-oracle matroids
• A scaling algorithm for weighted f-factors in general graphs
• Spectral sparsification via bounded-independence sampling
• High-accuracy multicommodity flows via iterative refinement
• Nested dissection meets IPMs: planar min-cost flow in nearly-linear time
• Negative-weight single-source shortest paths in near-linear time
• Small-space spectral sparsification via bounded-independence sampling
• Almost-linear-time weighted _p-norm solvers in slightly dense graphs via sparsification
• Parallel, distributed, and quantum exact single-source shortest paths with negative edge weights
• Lower bounds for adaptive relaxation-based algorithms for single-source shortest paths

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)