A polynomial projection-type algorithm for linear programming

2013/07/16 by Végh, László A., Zambelli, Giacomo
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1307.4334

Abstract

We propose a simple O([n⁵/log n]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 [4], where the recursion is replaced by a simple and more efficient iterative method. A similar approach was used in a more recent paper of Chubanov [6].

Related

• A Fast Polynomial-time Primal-Dual Projection Algorithm for Linear Programming
• A strongly polynomial-time algorithm for the general linear programming problem
• Validation of a strongly polynomial-time algorithm for the general linear programming problem
• A Polynomial Time Algorithm For 0-1 Integer Linear Programmings
• A numerical illustration of a recently proposed strongly polynomial-time algorithm for the general linear programming problem