Solving tall dense linear programs in nearly linear time

In this paper we provide an O ( 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 O (√ d )-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.

Authors

• Jan van den Brand
• Yin Tat Lee
• Aaron Sidford
• Zhao Song 0002

Keywords

• interior point method
• linear program
• nearly linear time