Article ID Journal Published Year Pages File Type
1142533 Operations Research Letters 2014 6 Pages PDF
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
, ,