Approximating Fractional Multicommodity Flow Independent of the Number of Commodities
From MaRDI portal
Publication:2706182
DOI10.1137/S0895480199355754zbMath0968.68068OpenAlexW2117595194MaRDI QIDQ2706182
Publication date: 19 March 2001
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895480199355754
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Combinatorial optimization (90C27)
Related Items (18)
Multiobjective optimization: Improved FPTAS for shortest paths and nonlinear objectives with applications ⋮ Costly circuits, submodular schedules and approximate Carathéodory theorems ⋮ Optimization in telecommunication networks ⋮ Unnamed Item ⋮ Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence ⋮ Scalable timing-aware network design via Lagrangian decomposition ⋮ Hardness Results for Structured Linear Systems ⋮ Algorithms for Finding Optimal Flows in Dynamic Networks ⋮ Unnamed Item ⋮ Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem ⋮ Metric inequalities and the network loading problem ⋮ A generalized approximation framework for fractional network flow and packing problems ⋮ Faster min-max resource sharing in theory and practice ⋮ Pricing for fairness: distributed resource allocation for multiple objectives ⋮ Short length Menger's theorem and reliable optical routing ⋮ Packing trees in communication networks ⋮ On three approaches to length-bounded maximum multicommodity flow with unit edge-lengths ⋮ Flows with unit path capacities and related packing and covering problems
This page was built for publication: Approximating Fractional Multicommodity Flow Independent of the Number of Commodities
