Area-convexity, _ regularization, and undirected multicommodity flow

DOI10.1145/3055399.3055501MaRDI QIDQ4977993zbMATH OpenOpenAlexFDO

Authors Jonah Sherman

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3055399.3055501

zbMATH Keywords

multicommodity flowarea convexityl-infinity regularization

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Ill-posedness and regularization problems in numerical linear algebra (65F22) Approximation algorithms (68W25) Flows in graphs (05C21) Miscellaneous inequalities involving matrices (15A45) Stochastic matrices (15B51)

Recommendations

• Flows in almost linear time via adaptive preconditioning
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• Faster approximate multicommodity flow using quadratically coupled flows
• Fast approximation algorithms for multicommodity flow problems
• A new approach to computing maximum flows using electrical flows

Cited in

(5)

• Generalized momentum-based methods: a Hamiltonian perspective
• Lower bounds for parallel and randomized convex optimization
• Accelerated Bregman Primal-Dual Methods Applied to Optimal Transport and Wasserstein Barycenter Problems
• Efficient convex optimization with oracles
• Unit Capacity Maxflow in Almost $m^{4/3}$ Time

This page was built for publication: Area-convexity, \(\ell_\infty\) regularization, and undirected multicommodity flow

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