A Friendly Smoothed Analysis of the Simplex Method (Q5129232)

scientific article; zbMATH DE number 7266063

Language	Label	Description	Also known as
English	A Friendly Smoothed Analysis of the Simplex Method	scientific article; zbMATH DE number 7266063

Statements

instance of

scholarly article

0 references

title

A Friendly Smoothed Analysis of the Simplex Method (English)

0 references

0 references

0 references

SIAM Journal on Computing

0 references

publication date

26 October 2020

0 references

full work available at URL

https://arxiv.org/abs/1711.05667

0 references

zbMATH Keywords

linear programming

0 references

shadow vertex simplex method

0 references

smoothed analysis

0 references

MaRDI profile type

Publication

0 references

cites work

The Hirsch Conjecture Holds for Normal Flag Complexes

0 references

A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps

0 references

A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension

0 references

Q4225299

0 references

Smoothed Analysis of the k-Means Method

0 references

Q4188659

0 references

The Hirsch Conjecture for Dual Transportation Polyhedra

0 references

Q4387224

0 references

An upper bound for the diameter of a polytope

0 references

A brief history of linear and mixed-integer programming computation

0 references

Q2712822

0 references

On sub-determinants and the diameter of polyhedra

0 references

Q3764803

0 references

Q3206654

0 references

The Average number of pivot steps required by the Simplex-Method is polynomial

0 references

Probabilistic analysis of optimization algorithms - some aspects from a practical point of view

0 references

A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes

0 references

Erratum: A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes

0 references

The diameters of network-flow polytopes satisfy the Hirsch conjecture

0 references

A linear bound on the diameter of the transportation polytope

0 references

Smoothed Analysis of the Successive Shortest Path Algorithm

0 references

Solving Totally Unimodular LPs with the Shadow Vertex Algorithm

0 references

On the shadow simplex method for curved polyhedra

0 references

A friendly smoothed analysis of the simplex method

0 references

Algorithms – ESA 2004

0 references

Q5808752

0 references

Graphs of transportation polytopes

0 references

On the smoothed complexity of convex hulls

0 references

Q2970468

0 references

A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees

0 references

Random walks, totally unimodular matrices, and a randomised dual simplex algorithm

0 references

Geometric random edge

0 references

Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP

0 references

Q3996150

0 references

Steepest-edge simplex algorithms for linear programming

0 references

A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games

0 references

Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

0 references

Use of dynamic trees in a network simplex algorithm for the maximum flow problem

0 references

Q4114709

0 references

A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time

0 references

Polynomial-time primal simplex algorithms for the minimum cost network flow problem

0 references

Efficient Shortest Path Simplex Algorithms

0 references

Worst case behavior of the steepest edge simplex method

0 references

An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm

0 references

Q4850043

0 references

Technical Note—A Polynomial Simplex Method for the Assignment Problem

0 references

The simplex algorithm with the pivot rule of maximizing criterion improvement

0 references

A quasi-polynomial bound for the diameter\\of graphs of polyhedra

0 references

A new polynomial-time algorithm for linear programming

0 references

A randomized polynomial-time simplex algorithm for linear programming

0 references

Q3050157

0 references

Q4051879

0 references

Paths on Polytopes

0 references

Bimatrix Equilibrium Points and Mathematical Programming

0 references

Q4530626

0 references

A subexponential bound for linear programming

0 references

The width of five-dimensional prismatoids

0 references

Q5187071

0 references

Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm

0 references

On the Implementation of a Primal-Dual Interior Point Method

0 references

Computational complexity of parametric linear programming

0 references

The Hirsch conjecture is true for (0,1)-polytopes

0 references

Polynomial dual network simplex algorithms

0 references

The Simplex Method is Strongly Polynomial for Deterministic Markov Decision Processes

0 references

A polynomial-time algorithm, based on Newton's method, for linear programming

0 references

Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices

0 references

A counterexample to the Hirsch conjecture

0 references

Q2930072

0 references

The Efficiency of the Simplex Method: A Survey

0 references

On the average number of steps of the simplex method of linear programming

0 references

Smoothed analysis of termination of linear programming algorithms

0 references

Smoothed analysis of algorithms

0 references

An asymptotically improved upper bound on the diameter of polyhedra

0 references

Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems

0 references

An Improved Kalai--Kleitman Bound for the Diameter of a Polyhedron

0 references

Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method

0 references

The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate

0 references

Identifiers

zbMATH Open document ID

1451.90095

0 references

DOI

10.1137/18M1197205

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5129232