Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142533 | Operations Research Letters | 2014 | 6 Pages |
Abstract
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).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
László A. Végh, Giacomo Zambelli,