The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption

摘要

In this paper, we show that the total number of distinct basic solutions generated by the simplex method using Tardos' basic algorithm is polynomially bounded in the number of constraints, the number of variables, and the maximum absolute value determinant of submatrices of a coefficient matrix. Tardos' basic algorithm generates auxiliary LP problems whose right-hand side vectors are scaled and rounded to integers. If the coefficient matrix is totally unimodular and all the auxiliary problems are nondegenerate, then the proposed simplex method is strongly polynomial. In the analysis of the algorithm, we use the recent results by Kitahara and Mizuno.