Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
type: Item
instance of: scholarly article
title: Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
zbMATH Open document ID: 0874.90085
DOI: 10.1007/BF02592195
author: M. D. Grigoriadis
author: Leonid G. Khachiyan
published in: Mathematical Programming. Series A. Series B
publication date: 1997-11-11T00:00:00Z
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 1046466
zbMATH Keywords: block-angular program
zbMATH Keywords: budget-constrained network flow
zbMATH Keywords: structured optimization
zbMATH Keywords: \(\varepsilon\)-approximate solution
zbMATH Keywords: cost-constrained \(K\)-commodity flow problem
zbMATH Keywords: approximate minimum-cost multicommodity flow
MaRDI profile type: Publication
cites work: Q3056948
cites work: Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
cites work: Coordination Complexity of Parallel Price-Directive Decomposition
cites work: A natural randomization strategy for multicommodity flow and related algorithms
cites work: Finding Minimum-Cost Circulations by Successive Approximation
cites work: Fast approximation algorithms for multicommodity flow problems
cites work: Q4234047
cites work: Q4886083
cites work: Fast Approximation Algorithms for Fractional Packing and Covering Problems
cites work: Q4886082
cites work: Q4215386
full work available at URL: https://doi.org/10.1007/bf02592195
OpenAlex ID: W330591652
Recommended article: Q4886083
Recommended article: Q3840370
Recommended article: Fast approximation algorithms for multicommodity flow problems
Recommended article: Approximation and Online Algorithms
Recommended article: Q3626409
Recommended article: Fast deterministic approximation for the multicommodity flow problem
Recommended article: Q4886082
Recommended article: An exact algorithm for a multicommodity min-cost flow over time problem
Recommended article: An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
description: scientific article; zbMATH DE number 1046466