The Average number of pivot steps required by the Simplex-Method is polynomial
From MaRDI portal
Publication:3950310
DOI10.1007/BF01917108zbMath0488.90047OpenAlexW2095007759MaRDI QIDQ3950310
Publication date: 1982
Published in: Zeitschrift für Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01917108
Related Items
On the length of simplex paths: The assignment case, Recognizing one-dimensional Euclidean preference profiles, A new family of exponential LP problems, On the efficiency of algorithms of analysis, A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps, Parametric linear programming and anti-cycling pivoting rules, Invertibility of random fredholm operators, Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm, A hybrid clustering algorithm, Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design, Polyhedral Combinatorics in Combinatorial Optimization, Efficient GPU-based implementations of simplex type algorithms, Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks, Experiments with external pivoting, A Friendly Smoothed Analysis of the Simplex Method, Applications of the parametric programming procedure, 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, 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, Computing \(c\)-optimal experimental designs using the simplex method of linear programming, Application of the ellipsoid method in an interactive procedure for multicriteria linear programming, An empirical analysis of heuristics for solving the two-machine flow shop problem with job release times, New results on the average behavior of simplex algorithms, On the average number of steps of the simplex method of linear programming, A note on the complexity of an algorithm for Chebyshev approximation, The complex interior-boundary method for linear and nonlinear programming with linear constraints, Regional complexity analysis of algorithms for nonconvex smooth optimization, Iterative computation of security strategies of matrix games with growing action set, Unnamed Item, Fast quantum subroutines for the simplex method, On the asymptotic average number of efficient vertices in multiple objective linear programming, Fast finite methods for a system of linear inequalities, Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems, Geometry of the Gass-Saaty parametric cost LP algorithm, The ellipsoid method and its implications, Moser's shadow problem, An experimental investigation of a primal–dual exterior point simplexalgorithm, A new efficient primal dual simplex algorithm
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Worst case behavior of the steepest edge simplex method
- The simplex algorithm with the pivot rule of maximizing criterion improvement
- OnR.W. Llewellyn's rules to identify redundant constraints: A detailed critique and some generalizations
- The Probability that a Random Polytope is Bounded
- Basishäufigkeit bei linearen bestriktionen
- The convex hull of a random set of points
- Some results in probabilistic geometry
- Sur L'enveloppe convexe des nuages de points aleatoires dans Rn. I
- The complexity of linear programming
