Solving Multicommodity Flow Problems by an Approximation Scheme

DOI10.1137/S1052623401391907MaRDI QIDQ5317532zbMATH OpenOpenAlexFDO

Authors J. Villavicencio

Publication date 16 September 2005

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s1052623401391907

zbMATH Keywords

approximation algorithmLagrangian decompositionline searchmulticommodity flowresource sharing problemstructured optimization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Programming involving graphs or networks (90C35)

Recommendations

• Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
• scientific article; zbMATH DE number 1263177
• Approximating fractional multicommodity flow independent of the number of commodities
• Faster approximation schemes for fractional multicommodity flow problems
• scientific article; zbMATH DE number 1187163

Cited in

(20)

• The multiperiod assignment problem: A multicommodity network flow model and specialized branch and bound algorithm
• An augmented Lagrangian approach to multi-commodity flow problems with conversions
• Solving difficult multicommodity problems with a specialized interior-point algorithm
• Solution of stochastic problems of assessing the feasibility of multicommodity flows
• A heuristic solution procedure for multicommodity integer flows
• Approximate decomposition methods for the analysis of multicommodity flow routing in generalized queuing networks
• Single-Sink Multicommodity Flow with Side Constraints
• Relaxation methods for the strictly convex multicommodity flow problem with capacity constraints on individual commodities
• On three approaches to length-bounded maximum multicommodity flow with unit edge-lengths
• Solving Large-Scale Linear Multicommodity Flow Problems with an Active Set Strategy and Proximal-ACCPM
• Multicommodity flow problems with a bounded number of paths: A flow deviation approach
• The Multicommodity Multilevel Bottleneck Assignment Problem
• scientific article; zbMATH DE number 634022 (Why is no real title available?)
• scientific article; zbMATH DE number 1149401 (Why is no real title available?)
• A Bundle Type Dual-Ascent Approach to Linear Multicommodity Min-Cost Flow Problems
• Integer multicommodity flow problems
• Coordination Complexity of Parallel Price-Directive Decomposition
• scientific article; zbMATH DE number 7071840 (Why is no real title available?)
• Approximation and Online Algorithms
• An efficient approach to optimization of semi‐stable routing in multicommodity flow networks

This page was built for publication: Solving Multicommodity Flow Problems by an Approximation Scheme

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5317532)