A polynomial projection-type algorithm for linear programming
Végh, L. A.
& Zambelli, G.
(2014).
A polynomial projection-type algorithm for linear programming.
Operations Research Letters,
42(1), 91-96.
https://doi.org/10.1016/j.orl.2013.12.007
& Zambelli, G.
(2014).
A polynomial projection-type algorithm for linear programming.
Operations Research Letters,
42(1), 91-96.
https://doi.org/10.1016/j.orl.2013.12.007
We propose a simple O([n5/logn]L)O([n5/logn]L) algorithm for linear programming feasibility, that can be considered as a polynomial-time implementation of the relaxation method. Our work draws from Chubanov’s “Divide-and-Conquer” 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).