The Average number of pivot steps required by the Simplex-Method is polynomial
From MaRDI portal
Cites work
- Basishäufigkeit bei linearen bestriktionen
- scientific article; zbMATH DE number 3644821 (Why is no real title available?)
- scientific article; zbMATH DE number 3648423 (Why is no real title available?)
- scientific article; zbMATH DE number 3706235 (Why is no real title available?)
- scientific article; zbMATH DE number 3708090 (Why is no real title available?)
- scientific article; zbMATH DE number 3726093 (Why is no real title available?)
- scientific article; zbMATH DE number 3626518 (Why is no real title available?)
- OnR.W. Llewellyn's rules to identify redundant constraints: A detailed critique and some generalizations
- Some results in probabilistic geometry
- Sur L'enveloppe convexe des nuages de points aleatoires dans Rn. I
- The complexity of linear programming
- The convex hull of a random set of points
- The Probability that a Random Polytope is Bounded
- The simplex algorithm with the pivot rule of maximizing criterion improvement
- What is the worst case behavior of the simplex algorithm?
- Worst case behavior of the steepest edge simplex method
Cited in
(44)- A new family of exponential LP problems
- A simplex variant solving an m d linear program in O(min(m 2,d 2)) expected number of pivot steps
- Parametric linear programming and anti-cycling pivoting rules
- Applications of the parametric programming procedure
- Polynomial-time primal simplex algorithms for the minimum cost network flow problem
- Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial
- On the asymptotic average number of efficient vertices in multiple objective linear programming
- An empirical analysis of heuristics for solving the two-machine flow shop problem with job release times
- Fast finite methods for a system of linear inequalities
- Geometry of the Gass-Saaty parametric cost LP algorithm
- The ellipsoid method and its implications
- A new efficient primal dual simplex algorithm
- Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks
- Regional complexity analysis of algorithms for nonconvex smooth optimization
- Fast quantum subroutines for the simplex method
- A note on the complexity of an algorithm for Chebyshev approximation
- Iterative computation of security strategies of matrix games with growing action set
- Moser's shadow problem
- Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design
- An experimental investigation of a primal-dual exterior point simplexalgorithm
- On the average number of steps of the simplex method of linear programming
- Application of the ellipsoid method in an interactive procedure for multicriteria linear programming
- New results on the average behavior of simplex algorithms
- Invertibility of random fredholm operators
- On the length of simplex paths: The assignment case
- On the efficiency of algorithms of analysis
- Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
- Polyhedral Combinatorics in Combinatorial Optimization
- Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
- The average number of pivot steps of the simplex-algorithm based on a generalized rotation-symmetry-model
- Exterior point simplex-type algorithms for linear and network optimization problems
- Smoothed and average-case approximation ratios of mechanisms: beyond the worst-case analysis
- A friendly smoothed analysis of the simplex method
- Upper and lower bounds on the smoothed complexity of the simplex method
- The NP-hard problem of computing the maximal sample variance over interval data is solvable in almost linear time with a high probability
- Upper and lower bounds on the smoothed complexity of the simplex method
- A unified worst case for classical simplex and policy iteration pivot rules
- Geometry-dependent matching pursuit: a transition phase for convergence on linear regression and Lasso
- Recognizing one-dimensional Euclidean preference profiles
- A hybrid clustering algorithm
- Efficient GPU-based implementations of simplex type algorithms
- Experiments with external pivoting
- Computing \(c\)-optimal experimental designs using the simplex method of linear programming
- The complex interior-boundary method for linear and nonlinear programming with linear constraints
This page was built for publication: The Average number of pivot steps required by the Simplex-Method is polynomial
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3950310)
