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

Abstract

Previous chapter Next chapter Full AccessProceedings Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Using Optimization to Break the Epsilon Barrier: A Faster and Simpler Width-Independent Algorithm for Solving Positive Linear Programs in ParallelZeyuan Allen-Zhu and Lorenzo OrecchiaZeyuan Allen-Zhu and Lorenzo Orecchiapp.1439 - 1456Chapter DOI:https://doi.org/10.1137/1.9781611973730.95PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We study the design of nearly-linear-time algorithms for approximately solving positive linear programs. Both the parallel and the sequential deterministic versions of these algorithms require Õ(ε−4) iterations, a dependence that has not been improved since the introduction of these methods in 1993 by Luby and Nisan. Moreover, previous algorithms and their analyses rely on update steps and convergence arguments that are combinatorial in nature, and do not seem to arise naturally from an optimization viewpoint. In this paper, we leverage insights from optimization theory to construct a novel algorithm that breaks the longstanding Õ(ε−4) barrier. Our algorithm has a simple analysis and a clear motivation. Our work introduces a number of novel techniques, such as the combined application of gradient descent and mirror descent, and a truncated, smoothed version of the standard multiplicative weight update, which may be of independent interest. Previous chapter Next chapter RelatedDetails Published:2015ISBN:978-1-61197-374-7eISBN:978-1-61197-373-0 https://doi.org/10.1137/1.9781611973730Book Series Name:ProceedingsBook Code:PRDA15Book Pages:viii + 2048

Locations

• arXiv (Cornell University) - PDF