On Chubanov's Method for Linear Programming
Amitabh Basu, Jesús A. De Loera, Mark Junod
INFORMS Journal on Computing · 2014 · Volume 26 · Issue 2
Abstract
We discuss the method recently proposed by S. Chubanov [Chubanov S (2012a) A strongly polynomial algorithm for linear systems having a binary solution. Math. Programming 134(3):533–570] for the linear feasibility problem. We present new, concise proofs and geometric interpretations of some of his results. From our ideas we derive the first strongly polynomial time algorithm based on relaxation method techniques for special classes of linear feasibility problems. Under certain conditions, these results provide new proofs of classical results obtained by Tardos for combinatorial linear programs. The paper ends with some experimental investigations.
Keywords
linear programming, relaxation methods, strongly polynomial time algorithms
Enable JavaScript for citation tools and additional paper interactions.