Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
From MaRDI portal
Publication:5386216
DOI10.1137/S0097539704446232zbMath1137.90014OpenAlexW2122205547MaRDI QIDQ5386216
Publication date: 22 April 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539704446232
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 (43)
On the complexity and approximability of budget-constrained minimum cost flows ⋮ Algorithms for multiplayer multicommodity flow problems ⋮ Greedy distributed optimization of multi-commodity flows ⋮ Fast approximation for computing the fractional arboricity and extraction of communities of a graph ⋮ Costly circuits, submodular schedules and approximate Carathéodory theorems ⋮ Finding Sparse Solutions for Packing and Covering Semidefinite Programs ⋮ A simple method for convex optimization in the oracle model ⋮ Combining Lagrangian decomposition and excessive gap smoothing technique for solving large-scale separable convex optimization problems ⋮ Solving MIPs via scaling-based augmentation ⋮ On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms ⋮ Unnamed Item ⋮ Efficient Primal-Dual Graph Algorithms for MapReduce ⋮ A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs ⋮ Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence ⋮ On the adaptivity gap of stochastic orienteering ⋮ Scalable timing-aware network design via Lagrangian decomposition ⋮ The Maximum Energy-Constrained Dynamic Flow Problem ⋮ Hardness Results for Structured Linear Systems ⋮ Numerical Structure of the Hessian of the Lagrange Dual Function for a Class of Convex Problems ⋮ On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow ⋮ Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games ⋮ The Maximum Flow Problem for Oriented Flows ⋮ Bin covering with cardinality constraints ⋮ Greedy algorithms for the single-demand facility location problem ⋮ Fast approximation of matroid packing and covering ⋮ Prolong the Lifetime of Wireless Sensor Networks Through Mobility: A General Optimization Framework ⋮ Fractional Set Cover in the Streaming Model. ⋮ A nearly linear-time PTAS for explicit fractional packing and covering linear programs ⋮ Nesterov's smoothing and excessive gap methods for an optimization problem in VLSI placement ⋮ Fast and Deterministic Approximations for k-Cut. ⋮ Towards more practical linear programming-based techniques for algorithmic mechanism design ⋮ On integer balancing of directed graphs ⋮ A generalized approximation framework for fractional network flow and packing problems ⋮ Mobile facility location: combinatorial filtering via weighted occupancy ⋮ On the approximability of robust network design ⋮ Faster min-max resource sharing in theory and practice ⋮ Unnamed Item ⋮ Maximum flows in generalized processing networks ⋮ Short length Menger's theorem and reliable optical routing ⋮ Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs ⋮ On randomized fictitious play for approximating saddle points over convex sets ⋮ Algorithms and Simulation Methods for Topology-Aware Sensor Networks ⋮ How the Experts Algorithm Can Help Solve LPs Online
This page was built for publication: Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
