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

DOI10.1007/BF01580645zbMATH Open0618.90061MaRDI QIDQ3755229FDOQ3755229

Nimrod Megiddo

Publication date: 1986

Published in: Mathematical Programming (Search for Journal in Brave)

Recommendations

• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
• scientific article; zbMATH DE number 3880432
• scientific article; zbMATH DE number 3898607
• The average number of pivot steps of the simplex-algorithm based on a generalized rotation-symmetry-model
• A Family of Simplex Variants Solving an m × d Linear Program in Expected Number of Pivot Steps Depending on d Only

zbMATH Keywords

spherical symmetryprobabilistic analysisaverage number of stepsself-dual simplex algorithm

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Bimatrix Equilibrium Points and Mathematical Programming
• Linear Programming in Linear Time When the Dimension Is Fixed
• New Finite Pivoting Rules for the Simplex Method
• A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
• Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
• Title not available (Why is that?)
• The Average number of pivot steps required by the Simplex-Method is polynomial
• On the average number of steps of the simplex method of linear programming
• A Family of Simplex Variants Solving an m × d Linear Program in Expected Number of Pivot Steps Depending on d Only
• Title not available (Why is that?)
• New results on the average behavior of simplex algorithms
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
• On the expected number of linear complementarity cones intersected by random and semi-random rays
• Title not available (Why is that?)

Cited In (13)

• A Friendly Smoothed Analysis of the Simplex Method
• Parametric linear programming and anti-cycling pivoting rules
• New results on the average behavior of simplex algorithms
• Title not available (Why is that?)
• An algorithm for disjunctive programs
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
• A tree traversal algorithm for decision problems in knot theory and 3-manifold topology
• Title not available (Why is that?)
• Upper and lower bounds on the smoothed complexity of the simplex method
• An asymptotic estimate of the average number of steps of the parametric simplex method
• A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
• Title not available (Why is that?)
• George Dantzig's impact on the theory of computation

This page was built for publication: Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm

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