Faster approximate multicommodity flow using quadratically coupled flows

DOI10.1145/2213977.2213979MaRDI QIDQ5415461zbMATH OpenOpenAlexFDO

Authors Jonathan Kelner, Richard Peng, Gary L. Miller

Publication date 13 May 2014

Published in Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.3367

zbMATH Keywords

multiplicative weights update methodmulticommodity flow problemsLaplacian linear systems

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Flows in graphs (05C21)

Abstract: The maximum multicommodity flow problem is a natural generalization of the maximum flow problem to route multiple distinct flows. Obtaining a $1-epsilon$ approximation to the multicommodity flow problem on graphs is a well-studied problem. In this paper we present an adaptation of recent advances in single-commodity flow algorithms to this problem. As the underlying linear systems in the electrical problems of multicommodity flow problems are no longer Laplacians, our approach is tailored to generate specialized systems which can be preconditioned and solved efficiently using Laplacians. Given an undirected graph with m edges and k commodities, we give algorithms that find $1-epsilon$ approximate solutions to the maximum concurrent flow problem and the maximum weighted multicommodity flow problem in time $ildeO(m^{4/3}poly(k,epsilo{n}^{-1}))$.

Recommendations

• Fast approximation algorithms for multicommodity flow problems
• Fast deterministic approximation for the multicommodity flow problem
• Approximating fractional multicommodity flow independent of the number of commodities
• A new approach to computing maximum flows using electrical flows
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations

Cited in

(11)

• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• Hardness results for structured linear systems
• scientific article; zbMATH DE number 7378710 (Why is no real title available?)
• Improving an interior-point algorithm for multicommodity flows by quadratic regularizations
• High-accuracy multicommodity flows via iterative refinement
• Speeding up Karmarkar's algorithm for multicommodity flows
• Faster approximation schemes for fractional multicommodity flow problems
• Unit Capacity Maxflow in Almost $m^{4/3}$ Time
• Analyzing quadratic unconstrained binary optimization problems via multicommodity flows
• Area-convexity, _ regularization, and undirected multicommodity flow
• Maximum flow and minimum-cost flow in almost-linear time

This page was built for publication: Faster approximate multicommodity flow using quadratically coupled flows

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