Journal article
A primal-simplex based Tardos’ algorithm
Abstract
In the mid-eighties Tardos proposed a strongly polynomial algorithm for solving linear programming problems for which the size of the coefficient matrix is polynomially bounded in the dimension of the input. Combining Orlin’s primal-based modification and Mizuno’s use of the simplex method, we introduce a modification of Tardos’ algorithm considering only the primal problem and using the simplex method to solve the auxiliary problems. The …
Authors
Mizuno S; Sukegawa N; Deza A
Journal
Operations Research Letters, Vol. 43, No. 6, pp. 625–628
Publisher
Elsevier
Publication Date
11 2015
DOI
10.1016/j.orl.2015.10.002
ISSN
0167-6377