On Chubanov's method for linear programming

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
1. Introduction In their now classical papers, Agmon (1954) and Motzkin and Schoenberg (1954) introduced the so called relaxation method to determine the feasibility of a system of linear inequalities [...]