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

Cites Work

Title not available (Why is that?)
Stochastic and Integral Geometry
On Polyhedral Approximations of the Second-Order Cone
Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
A subexponential bound for linear programming
The Efficiency of the Simplex Method: A Survey
Smoothed analysis of algorithms
Parametric Objective Function (Part 1)
A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
The simplex method. A probabilistic analysis
A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games
Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
Computational complexity of parametric linear programming
The Average number of pivot steps required by the Simplex-Method is polynomial
An extended conic formulation for geometric optimization
Title not available (Why is that?)
On the average number of steps of the simplex method of linear programming
Title not available (Why is that?)
The simplex algorithm with the pivot rule of maximizing criterion improvement
Title not available (Why is that?)
Worst case behavior of the steepest edge simplex method
Smoothed Analysis of the Simplex Method
Algorithms – ESA 2004
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
Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
A Friendly Smoothed Analysis of the Simplex Method
A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes
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

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