A friendly smoothed analysis of the simplex method (Q5129232)

scientific article; zbMATH DE number 7266063

Language	Label	Description	Also known as
default for all languages	No label defined
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

MaRDI publication profile

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

MIP: Theory and practice -- closing the gap

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

Smoothed complexity of convex hulls by witnesses and collectors

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

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

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