In this paper, we study fast first-order algorithms that approximately solve linear programs (LPs). More specifically, we apply algorithms from online linear programming to offline LPs and derive algorithms that are free of any matrix multiplication. To further improve the applicability of the proposed methods, we propose a variable-duplication technique that achieves $\mathcal{O}(\sqrt{mn/K})$ optimality gap by copying each variable $K$ times. Moreover, we identify that online algorithms can be efficiently incorporated into a column generation framework for large-scale LPs. Finally, numerical experiments show that our proposed methods can be applied either as an approximate direct solver or as an initialization subroutine in frameworks of exact LP solving.

翻译：在本文中,我们研究大约解决线性程序(LPs)的快速一阶算法。更具体地说,我们将在线线性编程的算法应用到离线性编程中下线性编程,并推算出不包含任何矩阵乘法的算法。为了进一步改善拟议方法的适用性,我们建议了一种可变的重复技术,通过复制每个变量的1K美元来达到1美元的最佳性差距。此外,我们确定在线算法可以有效地纳入大型 LPs的柱体生成框架。最后,数字实验表明,我们拟议的方法可以作为近似直接解答器或作为精确的LP解算框架中的初始化子例程。