HOW GOOD IS THE SIMPLEX ALGORITHM

By V. Klee, G. Minty. 1970

How researchers see this paper

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

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”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, methodology): “On a related note, active-set methods such that the simplex and min-norm-point algorithms may in general take exponentially many steps [120].”
Interior Methods for Nonlinear Optimization (2002, methodology): “In fact, with standard pivoting rules specifying the constraint to be dropped and added at each iteration, the simplex method can visit every vertex of the feasible region [64]; thus its worst-case complexity is exponential in the problem dimension.”
An Update on the Hirsch Conjecture (2009, background): “The a priori best pivot rule, the one originally proposed by Dantzig, is “move along the edge with maximum gradient”, but Klee and Minty [41] showed in 1972 that this can lead to paths of exponential length, even in polytopes combinatorially equivalent to cubes.”
Cones and interior-point algorithms for structured convex optimization involving powers andexponentials (2009, background): “In 1972 Klee and Minty ([34]) showed by an example that the worst-case complexity of the simplex method is in fact exponential in the size of the problem.”
The Earth Mover's Distance as a Metric for Image Retrieval (2000, unknown): “A theoretical analysis of the computational complexity of the transportation simplex is hard, since it is based on the simplex algorithm which can have, in general, an exponential worst case (Klee and Minty, 1972).”
Linear Optimization Problems with Inexact Data (2006, background): “Minty [72] who had shown by means of an example that the simplex method may take an exponential number of steps.”
On Partial Identification of the Pure Direct Effect (2015, methodology): “While the method used by this software is not guaranteed to converge at a polynomial rate (Klee and Minty, 1970), it is quite efficient in most cases (Schrijver, 1998).”
OSQP: an operator splitting solver for quadratic programs (2017, background): “However, the major drawback of activeset methods is that the worst-case complexity grows exponentially with the number of constraints, since it may be necessary to investigate all possible active-sets before reaching the optimal one [62].”
The NP-Completeness Column: An Ongoing Guide (1982, background): “The previous best worst-case bounds for this problem had been O(m n/2 ) [28].”
Linear Programming: Foundations and Extensions (1998, methodology): “Notes Techniques for exploiting sparsity in matrix factorization have their roots in the paper by Markowitz (1957). A few standard references on matrix factorization are the books of Duff et al. (1986), Golub & VanLoan (1989), and Gill et al. (1991). The eta-matrix technique given in Section 8.”
Settling the complexity of computing two-player Nash equilibria (2007, methodology): “It had been a challenge for some time (see Condon et al. [1999]) to explain why some algorithms, most notably the simplex algorithm for linear programming, though known to take exponential time in the worst case [Klee and Minty 1972], were nevertheless very fast in practice.”