Approximate minimum-cost multicommodity flows in O(^-2KNM) time
DOI10.1007/BF02592195zbMATH Open0874.90085OpenAlexW330591652MaRDI QIDQ1363422FDOQ1363422
Leonid G. Khachiyan, M. D. Grigoriadis
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
\(\varepsilon\)-approximate solutionapproximate minimum-cost multicommodity flowblock-angular programbudget-constrained network flowcost-constrained \(K\)-commodity flow problemstructured optimization
Deterministic network models in operations research (90B10) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Finding Minimum-Cost Circulations by Successive Approximation
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
- Coordination Complexity of Parallel Price-Directive Decomposition
- A natural randomization strategy for multicommodity flow and related algorithms
- Fast approximation algorithms for multicommodity flow problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (13)
- Title not available (Why is that?)
- Approximation algorithms for general packing problems and their application to the multicast congestion problem
- A natural randomization strategy for multicommodity flow and related algorithms
- Efficient Primal-Dual Graph Algorithms for MapReduce
- Title not available (Why is that?)
- Fast approximation algorithms for multicommodity flow problems
- Title not available (Why is that?)
- Multicast Routing and Design of Sparse Connectors
- Title not available (Why is that?)
- Barrier subgradient method
- Flows with unit path capacities and related packing and covering problems
- A penalty function heuristic for the resource constrained shortest path problem
- Scientific contributions of Leo Khachiyan (a short overview)
Recommendations
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Approximation and Online Algorithms 👍 👎
- Fast deterministic approximation for the multicommodity flow problem 👍 👎
- Fast approximation algorithms for multicommodity flow problems 👍 👎
- An exact algorithm for a multicommodity min-cost flow over time problem 👍 👎
- An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations 👍 👎
This page was built for publication: Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1363422)
