Validation of a recently proposed strongly polynomial-time algorithm for the general linear programming problem

Abstract

This article presents a validation of a recently proposed strongly polynomial-time algorithm for the general linear programming problem. The proposed algorithm is an implicit reduction procedure that combines primal and dual linear programming problems into a special system of linear equations constrained by complementarity relations and non-negative variables. Each iteration of the algorithm consists of applying a pair of complementary Gauss-Jordan pivoting operations, guided by a necessary-condition lemma. This validation article demonstrates that the proposed algorithm requires no more than 2(k+n) iterations, where k is the number of constraints and n is the number of variables of given general linear programming problem.

19 pages. Additional annotations have been provided for the proof of Lemma 6.1. A flow chart has just been added, as suggested by some readers. The results are the same as before. The description have been vastly improved as a result of suggestions by reputable journal reviewers and area editors