Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time

DOI10.1007/BF02592195zbMath0874.90085MaRDI QIDQ1363422

Michael D. Grigoriadis, Leonid G. Khachiyan

Publication date: 11 November 1997

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

\(\varepsilon\)-approximate solution; approximate minimum-cost multicommodity flow; block-angular program; budget-constrained network flow; cost-constrained \(K\)-commodity flow problem; structured optimization

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B10: Deterministic network models in operations research

Related Items

Barrier subgradient method, Approximation algorithms for general packing problems and their application to the multicast congestion problem, Scientific contributions of Leo Khachiyan (a short overview), Flows with unit path capacities and related packing and covering problems, A penalty function heuristic for the resource constrained shortest path problem, Efficient Primal-Dual Graph Algorithms for MapReduce, Multicast Routing and Design of Sparse Connectors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A natural randomization strategy for multicommodity flow and related algorithms
• Fast approximation algorithms for multicommodity flow problems
• Finding Minimum-Cost Circulations by Successive Approximation
• Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Coordination Complexity of Parallel Price-Directive Decomposition