Area-convexity, _ regularization, and undirected multicommodity flow

DOI10.1145/3055399.3055501zbMATH Open1370.90050OpenAlexW2624960300MaRDI QIDQ4977993FDOQ4977993

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

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

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)

Cited In (5)

• Accelerated Bregman Primal-Dual Methods Applied to Optimal Transport and Wasserstein Barycenter Problems
• Efficient convex optimization with oracles
• Generalized momentum-based methods: a Hamiltonian perspective
• Lower bounds for parallel and randomized convex optimization
• 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)