A Friendly Smoothed Analysis of the Simplex Method

DOI10.1137/18M1197205zbMath1451.90095arXiv1711.05667OpenAlexW3094140778MaRDI QIDQ5129232

Daniel Dadush, Sophie Huiberts

Publication date: 26 October 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1711.05667

zbMATH Keywords

linear programmingsmoothed analysisshadow vertex simplex method

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Linear programming (90C05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

The Polyhedral Geometry of Pivot Rules and Monotone Paths, Monotone paths on cross-polytopes, What Tropical Geometry Tells Us about the Complexity of Linear Programming, On the integrality gap of binary integer programs with Gaussian data

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A counterexample to the Hirsch conjecture
• Polynomial dual network simplex algorithms
• On the shadow simplex method for curved polyhedra
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
• A new polynomial-time algorithm for linear programming
• A linear bound on the diameter of the transportation polytope
• Graphs of transportation polytopes
• Probabilistic analysis of optimization algorithms - some aspects from a practical point of view
• A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Worst case behavior of the steepest edge simplex method
• Use of dynamic trees in a network simplex algorithm for the maximum flow problem
• Polynomial-time primal simplex algorithms for the minimum cost network flow problem
• An upper bound for the diameter of a polytope
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• Smoothed analysis of termination of linear programming algorithms
• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• Steepest-edge simplex algorithms for linear programming
• The Hirsch conjecture is true for (0,1)-polytopes
• A subexponential bound for linear programming
• A brief history of linear and mixed-integer programming computation
• An asymptotically improved upper bound on the diameter of polyhedra
• Geometric random edge
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
• The simplex algorithm with the pivot rule of maximizing criterion improvement
• Erratum: A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes
• The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
• A randomized polynomial-time simplex algorithm for linear programming
• An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
• Solving Totally Unimodular LPs with the Shadow Vertex 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
• A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees
• The Hirsch Conjecture for Dual Transportation Polyhedra
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• Smoothed Analysis of the Successive Shortest Path Algorithm
• The Simplex Method is Strongly Polynomial for Deterministic Markov Decision Processes
• Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
• Smoothed analysis of algorithms
• Technical Note—A Polynomial Simplex Method for the Assignment Problem
• 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
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• On the Implementation of a Primal-Dual Interior Point Method
• 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
• Efficient Shortest Path Simplex Algorithms
• A friendly smoothed analysis of the simplex method
• The width of five-dimensional prismatoids
• An Improved Kalai--Kleitman Bound for the Diameter of a Polyhedron
• The Hirsch Conjecture Holds for Normal Flag Complexes
• On the smoothed complexity of convex hulls
• Smoothed Analysis of the k-Means Method
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
• Algorithms – ESA 2004
• Bimatrix Equilibrium Points and Mathematical Programming
• Paths on Polytopes
• On sub-determinants and the diameter of polyhedra