The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption. (1st November 2016)

• Record Type: Journal Article
• Authors: Mizuno, S.
• Is Part Of: Optimization methods and software. Volume 31:Number 6(2016)
• Page Start: 1298
• Page End: 1304
• Publication Date: 2016-11-01
• Subjects: linear programming -- simplex method -- strongly polynomial algorithm -- totally unimodular matrix; 90C05 -- 11Y16; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2016.1208748
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : 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.