The Simplex Method: A Probabilistic Analysis

By K. Borgwardt. 1986

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Rémi Tachet des Combes
2. Kimia Nadjahi
3. Romain Laroche
4. Paul Trichelair
5. Santosh Srinivas Vempala
6. Imre Bárány
7. Adrian R. Vetta
8. Aviral Kumar

Citations in the corpus

• Safe Policy Improvement with Soft Baseline Bootstrapping (2019, background): “Even though the worst-case computational complexity of the simplex is exponential in the dimensions of the program being solved (Klee and Minty, 1972), this algorithm is efficient in practice: the number of iterations seems polynomial, and sometimes linear in the problem size (Borgwardt, 1987; Dantz”
• Safe Policy Improvement with Baseline Bootstrapping (2017, background): “Even though the worst-case computational complexity of the simplex is exponential in the dimensions of the program being solved (Klee and Minty, 1972), this algorithm is efficient in practice: the number of iterations seems polynomial, and sometimes linear in the problem size (Borgwardt, 1987; Dantz”
• Nash equilibria in random games (2005, methodology): “Motivated by the question of explaining the success of the simplex algorithm, Borgwardt [7], Smale [34] and Megiddo [25] studied linear programs where the constraints are chosen randomly from spherically symmetric distributions and showed that variants of the sim plex algorithm run in polynomial tim”