Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m10/7 log W) Time (Extended Abstract)

DOI10.1137/1.9781611974782.48zbMath1410.68291arXiv1605.01717OpenAlexW4249075686MaRDI QIDQ4575786

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

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) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Signed and weighted graphs (05C22) Flows in graphs (05C21)

Related Items (14)

Quadratically Regularized Optimal Transport on Graphs ⋮ Status determination by interior-point methods for convex optimization problems in domain-driven form ⋮ Unit Capacity Maxflow in Almost $m^{4/3}$ Time ⋮ Minimum-cost flows in unit-capacity networks ⋮ Minimum cost flow in the CONGEST model ⋮ Unnamed Item ⋮ Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model ⋮ Hardness Results for Structured Linear Systems ⋮ Embedding-preserving rectangle visibility representations of nonplanar graphs ⋮ Ortho-polygon visibility representations of 3-connected 1-plane graphs ⋮ Min-Cost Flow in Unit-Capacity Planar Graphs ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ Minimum cost \(b\)-matching problems with neighborhoods ⋮ Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC

This page was built for publication: Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m^10/7 log W) Time (Extended Abstract)