On the average number of steps of the simplex method of linear programming
From MaRDI portal
Publication:3040925
DOI10.1007/BF02591902zbMATH Open0526.90060MaRDI QIDQ3040925FDOQ3040925
Authors: Stephen Smale 
Publication date: 1983
Published in: Mathematical Programming (Search for Journal in Brave)
complexitysimplex methodpath followingaverage number of stepsDantzig's self-dual parametric algorithm
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The fundamental theorem of algebra and complexity theory
- Random polytopes: Their definition, generation and aggregate properties
- A convergent process of price adjustment and global Newton methods
- The Gauss-Bonnet Theorem for Riemannian Polyhedra
- Computational complexity of complementary pivot methods
- On the role of the Heisenberg group in harmonic analysis
- The Average number of pivot steps required by the Simplex-Method is polynomial
- The Solution of Systems of Piecewise Linear Equations
- Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On Algorithms for Solvingf(x)=0
- Complexity of linear programming
- A new linear programming algorithm - better or worse than the simplex method?
Cited In (49)
- Average polynomial time complexity of some NP-complete problems
- On the average speed of Lemke's algorithm for quadratic programming
- On the expected number of linear complementarity cones intersected by random and semi-random rays
- A new family of exponential LP problems
- A friendly smoothed analysis of the simplex method
- Asymptotic optimality of a transport-problem plan constructed by the minimum-element method
- Diophantine cryptography over infinite groups
- Invertibility of random fredholm operators
- A new simple homotopy algorithm for linear programming. I
- Parametric linear programming and anti-cycling pivoting rules
- Some remarks on Karmarkar's potential function
- Polyhedral Combinatorics in Combinatorial Optimization
- Recent developments in information-based complexity
- Experiments with external pivoting
- Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices
- Recognizing one-dimensional Euclidean preference profiles
- Optimal search algorithm for extrema of a discrete periodic bimodal function
- New results on the average behavior of simplex algorithms
- Regional complexity analysis of algorithms for nonconvex smooth optimization
- Quantitative simulations by matrices
- Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs
- Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial
- Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
- Exponential lower bounds for finding Brouwer fixed points
- Simplex-inspired algorithms for solving a class of convex programming problems
- Random linear programs with many variables and few constraints
- From Parity and Payoff Games to Linear Programming
- Polynomial algorithms for finding the asymptotically optimum plan of the multiindex axial assignment problem
- On Estimating Optimal Bases for Linear Programs
- Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
- Estimating the volume of solution space for satisfiability modulo linear real arithmetic
- On the efficiency of algorithms of analysis
- Upper and lower bounds on the smoothed complexity of the simplex method
- Polynomial-time primal simplex algorithms for the minimum cost network flow problem
- Random inequality constraint systems with few variables
- Probabilistic analysis of a differential equation for linear programming
- A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
- Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure.
- Average case optimality
- Statistical complexity of the power method for Markov chains
- A quadratically convergent method for linear programming
- Halting time is predictable for large models: a universality property and average-case analysis
- Conditioning of random conic systems under a general family of input distributions
- George Dantzig's impact on the theory of computation
- On the probabilistic complexity of finding an approximate solution for linear programming
- On probabilistic algorithm for solving almost all instances of the set partition problem
- Average number of iterations of some polynomial interior-point -- algorithms for linear programming
- Monotone meshfree methods for linear elliptic equations in non-divergence form via nonlocal relaxation
- Fast finite methods for a system of linear inequalities
This page was built for publication: On the average number of steps of the simplex method of linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3040925)
