Generalized preconditioning and undirected minimum-cost flow

DOI10.1137/1.9781611974782.49zbMATH Open1422.90063OpenAlexW4229679398MaRDI QIDQ4575787FDOQ4575787

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

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

Mathematics Subject Classification ID

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

Cited In (6)

• Title not available (Why is that?)
• A data-dependent approach for high-dimensional (robust) Wasserstein alignment
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• Quadratically regularized optimal transport on graphs
• Prim-based support-graph preconditioners for min-cost flow problems
• Preconditioning for the Geometric Transportation Problem

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)