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

DOI10.1007/BF02592195zbMath0874.90085OpenAlexW330591652MaRDI 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)

Full work available at URL: https://doi.org/10.1007/bf02592195

zbMATH Keywords

\(\varepsilon\)-approximate solutionapproximate minimum-cost multicommodity flowblock-angular programbudget-constrained network flowcost-constrained \(K\)-commodity flow problemstructured optimization

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10)

Related Items (8)

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time