Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
From MaRDI portal
Publication:4302277
DOI10.1137/S0097539792241175zbMath0809.68077OpenAlexW2010223239MaRDI QIDQ4302277
Éva Tardos, Serge A. Plotkin, Philip N. Klein, Clifford Stein
Publication date: 14 August 1994
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539792241175
Analysis of algorithms and problem complexity (68Q25) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Combinatorial optimization (90C27)
Related Items
Greedy distributed optimization of multi-commodity flows, An approximate max-flow min-cut relation for undirected multicommodity flow, with applications, Drawings of graphs on surfaces with few crossings, On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms, Improved approximations for the minimum-cut ratio and the flux, Unnamed Item, A fast polynomial time algorithm for logistics network flows, Approximation algorithms for general packing problems and their application to the multicast congestion problem, Fast approximation of minimum multicast congestion – Implementation VERSUS Theory, On the complexity of bandwidth allocation in radio networks, Constructing integral uniform flows in symmetric networks with application to the edge-forwarding index problem, Faster shortest-path algorithms for planar graphs, A combinatorial approximation algorithm for concurrent flow problem and its application, Self-concordant barriers for convex approximations of structured convex sets, Multicast Routing and Design of Sparse Connectors, Flows with unit path capacities and related packing and covering problems
