Generalized preconditioning and undirected minimum-cost flow

DOI10.1137/1.9781611974782.49MaRDI QIDQ4575787zbMATH OpenOpenAlexFDO

Authors Jonah Sherman

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://doi.org/10.1137/1.9781611974782.49

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Flows in almost linear time via adaptive preconditioning
• A new approach to computing maximum flows using electrical flows
• Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
• New algorithms for generalized network flows
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations

Cited in

(9)

• Prim-based support-graph preconditioners for min-cost flow problems
• Quadratically regularized optimal transport on graphs
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• Preconditioning for the Geometric Transportation Problem
• scientific article; zbMATH DE number 7561283 (Why is no real title available?)
• A data-dependent approach for high-dimensional (robust) Wasserstein alignment
• Optimal electrical oblivious routing on expanders
• Almost-linear-time weighted _p-norm solvers in slightly dense graphs via sparsification
• A simple deterministic near-linear time approximation scheme for transshipment with arbitrary positive edge costs

This page was built for publication: Generalized preconditioning and undirected minimum-cost flow

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