Reconciliation of Various Complexity and Condition Measures for Linear Programming Problems and a Generalization of Tardos' Theorem

Jackie C. K. Ho and Levent Tuncel

First, we review and clarify the relationships amongst various complexity and condition measures for linear programming problems. Then, we generalize Tardos' Theorem for linear programming problems with integer data to linear programming problems with real number data. Our generalization, in contrast to the only previous such generalization due to Vavasis and Ye, shows that many conventional, polynomial-time (in the sense of the Turing Machine Model, with integer data) primal-dual interior-point algorithms can be adapted in a Tardos' like scheme, to solve linear programming problems with real number data in time polynomial in the dimensions of the coefficient matrix and the logarithms of certain measures of the coefficient matrix (independent of the objective function and the right-hand-side vectors).

Research Report CORR2000-33, Department of Combinatorics and Optimization, University of Waterloo, Ontario, Canada, June 12 2000.