On the probabilistic complexity of finding an approximate solution for linear programming (Q2483208)

The authors study the problem of finding an \(\varepsilon\)-optimal solution to a real-life linear program. They begin with a useful overview of the literature on existing probabilistic and worst-case estimations of the complexity of solving linear programs and then continue by presenting their probabilistic model for which they then describe (with proof) asymptotic results, convergence properties and average number of iterations required to obtain a solution with a value within \(\varepsilon\) of the optimal. Several useful theorems are proven in the course of this paper, which concludes with a list of very useful references.