A polynomial projection-type algorithm for linear programming

作者：Vegh Laszlo A; Zambelli Giacomo^*

来源：Operations Research Letters, 2014, 42(1): 91-96.

DOI：10.1016/j.orl.2013.12.007

• Linear programming
• Polynomial-time algorithms
• Relaxation method

We propose a simple O(vertical bar n(5)/log n vertical bar L) algorithm for linear programming feasibility, that can be considered as a polynomial-time implementation of the relaxation method. Our work draws from Chubanov%26apos;s %26quot;Divide-and-Conquer%26quot; algorithm (Chubanov, 2012), with the recursion replaced by a simple and more efficient iterative method. A similar approach was used in a more recent paper of Chubanov (2013).

• 出版日期2014-1