论文标题
在几乎线性的时间内解决高密集的线性程序
Solving Tall Dense Linear Programs in Nearly Linear Time
论文作者
论文摘要
在本文中，我们提供了一个$ \ tilde {o}（nd+d^{3}）$ time随机算法，用于求解具有$ d $变量的线性程序和具有很高概率的$ n $约束。 To obtain this result we provide a robust, primal-dual $\tilde{O}(\sqrt{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.有趣的是，我们在不使用快速矩阵乘法的情况下获得了此运行时间，因此，除非在线性系统求解中取得重大进展，否则我们的运行时间对于在不使用快速矩阵乘法的算法中求解密集的线性程序几乎是最佳的。
In this paper we provide an $\tilde{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 $\tilde{O}(\sqrt{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.
