Solving linear programs with finite precision: I. Condition numbers and random programs

We define a condition number (A,b,c) for a linear program min x s.t. Ax=b,x0 and give two characterizations via distances to degeneracy and singularity. We also give bounds for the expected value, as well as for higher moments, of log (A,b,c) when the entries of A,b and c are i.i.d. random variables with normal distribution. This work has been substantially funded by a grant from the Research Grants Council of the Hong Kong SAR (project number CityU 1085/02P)