15 November 2001
Dr Raphael Hauser
(Joint work with Felipe Cucker and Dennis Cheung, City University of Hong Kong.) \\ \\ Condition numbers are important complexity-theoretic tools to capture a "distillation" of the input aspects of a computational problem that determine the running time of algorithms for its solution and the sensitivity of the computed output. The motivation for our work is the desire to understand the average case behaviour of linear programming algorithms for a large class of randomly generated input data in the computational model of a machine that computes with real numbers. In this model it is not known whether linear programming is polynomial time solvable, or so-called "strongly polynomial". Closely related to linear programming is the problem of either proving non-existence of or finding an explicit example of a point in a polyhedral cone defined in terms of certain input data. A natural condition number for this computational problem was developed by Cheung and Cucker, and we analyse its distributions under a rather general family of input distributions. We distinguish random sampling of primal and dual constraints respectively, two cases that necessitate completely different techniques of analysis. We derive the exact exponents of the decay rates of the distribution tails and prove various limit theorems of complexity theoretic importance. An interesting result is that the existence of the k-th moment of Cheung-Cucker's condition number depends only very mildly on the distribution of the input data. Our results also form the basis for a second paper in which we analyse the distributions of Renegar's condition number for the randomly generated linear programming problem.
- Computational Mathematics and Applications Seminar