Approximate minimum-cost multicommodity flows in O(^-2KNM) time
From MaRDI portal
Publication:1363422
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
Cites work
- scientific article; zbMATH DE number 1215271 (Why is no real title available?)
- scientific article; zbMATH DE number 1263177 (Why is no real title available?)
- scientific article; zbMATH DE number 910906 (Why is no real title available?)
- scientific article; zbMATH DE number 910907 (Why is no real title available?)
- A natural randomization strategy for multicommodity flow and related algorithms
- Coordination Complexity of Parallel Price-Directive Decomposition
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
- Fast approximation algorithms for multicommodity flow problems
- Finding Minimum-Cost Circulations by Successive Approximation
- Network flows. Theory, algorithms, and applications.
Cited in
(23)- Multicommodity network flows: A survey. II: Solution methods
- scientific article; zbMATH DE number 1187163 (Why is no real title available?)
- scientific article; zbMATH DE number 515936 (Why is no real title available?)
- 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
- scientific article; zbMATH DE number 910907 (Why is no real title available?)
- On the complexity and approximability of budget-constrained minimum cost flows
- Fast approximation algorithms for multicommodity flow problems
- Generalized preconditioning and undirected minimum-cost flow
- Fast and simple approximation schemes for generalized flow.
- Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
- scientific article; zbMATH DE number 910906 (Why is no real title available?)
- 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)
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)
