Using Optimization to Break the Epsilon Barrier: A Faster and Simpler Width-Independent Algorithm for Solving Positive Linear Programs in Parallel

DOI10.1137/1.9781611973730.95zbMath1371.68317OpenAlexW2157604254MaRDI QIDQ5363010

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Parallel algorithms in computer science (68W10)

Related Items (10)

Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method ⋮ 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 ⋮ Non-linear ski rental ⋮ Reconstructing Markov processes from independent and anonymous experiments ⋮ Fair Packing and Covering on a Relative Scale ⋮ Fractional Set Cover in the Streaming Model. ⋮ Unnamed Item ⋮ Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling ⋮ Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent

This page was built for publication: Using Optimization to Break the Epsilon Barrier: A Faster and Simpler Width-Independent Algorithm for Solving Positive Linear Programs in Parallel