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

Cites work

scientific article; zbMATH DE number 3466805 (Why is no real title available?)
scientific article; zbMATH DE number 3538744 (Why is no real title available?)
scientific article; zbMATH DE number 3626518 (Why is no real title available?)
scientific article; zbMATH DE number 1241836 (Why is no real title available?)
scientific article; zbMATH DE number 653033 (Why is no real title available?)
A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes
A friendly smoothed analysis of the simplex method
A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
A subexponential bound for linear programming
A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games
Algorithms – ESA 2004
An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
An exponential lower bound for Zadeh's pivot rule
An extended conic formulation for geometric optimization
Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
Computational complexity of parametric linear programming
Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
Linear optimization with the shadow vertex algorithm in the context of probabilistic analyses. Studies on the transition from phase 1 to phase 2 in the average-case analysis and in the smoothing analysis of the simplex method
On Polyhedral Approximations of the Second-Order Cone
On the average number of steps of the simplex method of linear programming
Parametric objective function. I
Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
Smoothed Analysis of the Simplex Method
Smoothed analysis of algorithms
Smoothed complexity of convex hulls by witnesses and collectors
Stochastic and Integral Geometry
Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
The Average number of pivot steps required by the Simplex-Method is polynomial
The Efficiency of the Simplex Method: A Survey
The simplex algorithm with the pivot rule of maximizing criterion improvement
The simplex method. A probabilistic analysis
Worst case behavior of the steepest edge simplex method

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499348)