Approximate minimum-cost multicommodity flows in O(^-2KNM) time
DOI10.1007/BF02592195zbMATH Open0874.90085OpenAlexW330591652MaRDI QIDQ1363422FDOQ1363422
Authors: M. 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
Recommendations
- Publication:4886083
- scientific article; zbMATH DE number 1187163
- Fast approximation algorithms for multicommodity flow problems
- Approximation and Online Algorithms
- An \(O(nm^ 2)\) time algorithm for solving minimal cost network flow problems
- Fast deterministic approximation for the multicommodity flow problem
- Publication:4886082
- 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
\(\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
- Network flows. Theory, algorithms, and applications.
- Finding Minimum-Cost Circulations by Successive Approximation
- Title not available (Why is that?)
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Title not available (Why is that?)
- 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?)
Cited In (23)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Efficient Algorithms for Separated Continuous Linear Programs: The Multicommodity Flow Problem with Holding Costs and Extensions
- Efficient primal-dual graph algorithms for MapReduce
- Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks
- Approximation algorithms for general packing problems and their application to the multicast congestion problem
- A natural randomization strategy for multicommodity flow and related algorithms
- Title not available (Why is that?)
- On the complexity and approximability of budget-constrained minimum cost flows
- Generalized preconditioning and undirected minimum-cost flow
- Fast approximation algorithms for multicommodity flow problems
- Fast and simple approximation schemes for generalized flow.
- Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
- Title not available (Why is that?)
- Multicast Routing and Design of Sparse Connectors
- A scaling algorithm for multicommodity flow problems
- Barrier subgradient method
- Flows with unit path capacities and related packing and covering problems
- Solving Multicommodity Flow Problems by an Approximation Scheme
- A penalty function heuristic for the resource constrained shortest path problem
- Algorithms – ESA 2005
- Scientific contributions of Leo Khachiyan (a short overview)
- Multicommodity network flows: A survey. II: Solution methods
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)
