The Simplex Method

0 Introduction.- Formulation of the problem and basic notation.- 1 The problem.- A Historical Overview.- 2 The gap between worst case and practical experience.- 3 Alternative algorithms.- 4 Results of stochastic geometry.- 5 The results of the author.- 6 The work of Smale.- 7 The paper of Haimovich.- 8 Quadratic expected number of steps for sign-invariance model.- Discussion of different stochastic models.- 9 What is the "Real World Model"?.- Outline of Chapters 1-5.- 10 The basic ideas and the methods of this book.- 11 The results of this book.- 12 Conclusion and conjectures.- 1 The Shadow-Vertex Algorithm.- 1 Primal interpretation.- 2 Dual interpretation.- 3 Numerical realization of the algorithm.- 4 The algorithm for Phase I.- 2 The Average Number of Pivot Steps.- 1 The probability space.- 2 An integral formula for the expected number of S.- 3 A transformation of coordinates.- 4 Generalizations.- 3 The Polynomiality of the Expected Number of Steps.- 1 Comparison of two integrals.- 2 An application of Cavalieri's Principle.- 3 The influence of the distribution.- 4 Evaluation of the quotient.- 5 The average number of steps in our complete Simplex-Method.- 4 Asymptotic Results.- 1 An asymptotic upper bound in integral form.- 2 Asymptotic results for certain classes of distributions.- 3 Special distributions with bounded support.- 4 Asymptotic bounds under uniform distributions.- 5 Asymptotic bounds under Gaussian distribution.- 5 Problems with Nonnegativity Constraints.- 1 The geometry.- 2 The complete solution method.- 3 A simplification of the boundary-condition.- 4 Explicit formulation of the intersection-condition.- 5 Componentwise sign-independence and the intersection condition.- 6 The average number of pivot steps.- 6 Appendix.- 1 Gammafunction andBetafunction.- 2 Unit ball and unit sphere.- 3 Estimations under variation of the weights.- References.