Upper and lower bounds on the smoothed complexity of the simplex method

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
The simplex method. A probabilistic analysis
A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
Worst case behavior of the steepest edge simplex method
A subexponential bound for linear programming
The simplex algorithm with the pivot rule of maximizing criterion improvement
An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games
On the average number of steps of the simplex method of linear programming
Stochastic and Integral Geometry
Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
Smoothed analysis of algorithms
The Efficiency of the Simplex Method: A Survey
Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
Computational complexity of parametric linear programming
The Average number of pivot steps required by the Simplex-Method is polynomial
Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes
Smoothed Analysis of the Simplex Method
A Friendly Smoothed Analysis of the Simplex Method
Parametric Objective Function (Part 1)
Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
Algorithms – ESA 2004
On Polyhedral Approximations of the Second-Order Cone
An exponential lower bound for Zadeh's pivot rule

This page was built for publication: Upper and lower bounds on the smoothed complexity of the simplex method