Solving Tall Dense Linear Programs in Nearly Linear Time

DOI10.1145/3357713.3384309MaRDI QIDQ6334245arXivFDO

Authors Jan van Den Brand, Yin Tat Lee, Aaron Sidford, Zhao Song

Publication date 6 February 2020

Published in arXiv

Full work available at URL https://doi.org/10.1145/3357713.3384309

Mathematics Subject Classification ID

Theory of computing (68Qxx)

arXiv classification

cs.DSmath.OC

Abstract: In this paper we provide an $ildeO(nd+d^3)$ time randomized algorithm for solving linear programs with $d$ variables and $n$ constraints with high probability. To obtain this result we provide a robust, primal-dual $ildeO(sqrtd)$-iteration interior point method inspired by the methods of Lee and Sidford (2014, 2019) and show how to efficiently implement this method using new data-structures based on heavy-hitters, the Johnson-Lindenstrauss lemma, and inverse maintenance. Interestingly, we obtain this running time without using fast matrix multiplication and consequently, barring a major advance in linear system solving, our running time is near optimal for solving dense linear programs among algorithms that do not use fast matrix multiplication.

This page was built for publication: Solving Tall Dense Linear Programs in Nearly Linear Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6334245)