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

Laplacian linear systemsmulticommodity flow problemsmultiplicative weights update method

Mathematics Subject Classification ID

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

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)

• Speeding up Karmarkar's algorithm for multicommodity flows
• Improving an interior-point algorithm for multicommodity flows by quadratic regularizations
• Faster approximation schemes for fractional multicommodity flow problems
• Area-convexity, _ regularization, and undirected multicommodity flow
• Dynamic effective resistances and approximate Schur complement on separable graphs
• Unit Capacity Maxflow in Almost $m^{4/3}$ Time
• Hardness results for structured linear systems
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• High-accuracy multicommodity flows via iterative refinement
• Maximum flow and minimum-cost flow in almost-linear time
• Analyzing quadratic unconstrained binary optimization problems via multicommodity flows

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)