## 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.

Contact: ltuncel@math.uwaterloo.ca