The average number of pivot steps of the simplex-algorithm based on a generalized rotation-symmetry-model

DOI10.1007/S00186-014-0483-8MaRDI QIDQ486944zbMATH OpenOpenAlexFDO

Authors Markus Göhl, K. H. Borgwardt

Publication date 19 January 2015

Published in Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL https://nbn-resolving.org/urn:nbn:de:bvb:384-opus4-27649

zbMATH Keywords

linear programmingstochastic geometryprobabilistic analysissimplex methodaverage case analysisrotation symmetry model

Mathematics Subject Classification ID

Linear programming (90C05) Geometric probability and stochastic geometry (60D05) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Recommendations

• Empirical Studies on the Average Efficiency of Simplex Variants under Rotation Symmetry
• scientific article; zbMATH DE number 3898607
• The average computing time of the simplex method in a generalized rotational symmetry model
• A lower bound on the average number of pivot-steps for solving linear programs. Valid for all variants of the simplex-algorithm
• On the variance of the number of pivot steps required by the simplex algorithm

Cites work

• scientific article; zbMATH DE number 3648423 (Why is no real title available?)
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 803180 (Why is no real title available?)
• scientific article; zbMATH DE number 3069632 (Why is no real title available?)
• Average-case analysis of the double description method and the beneath-beyond algorithm
• Erratum: ``A sharp upper bound for the expected number of shadow vertices in LP-polyhedra under orthogonal projection on two-dimensional planes
• The Average number of pivot steps required by the Simplex-Method is polynomial
• The average computing time of the simplex method in a generalized rotational symmetry model
• The simplex method. A probabilistic analysis
• �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten

Cited in

(5)

• On a relationship between record values and Ross’s model of algorithm efficiency
• Empirical Studies on the Average Efficiency of Simplex Variants under Rotation Symmetry
• Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
• The average computing time of the simplex method in a generalized rotational symmetry model
• On the variance of the number of pivot steps required by the simplex algorithm

This page was built for publication: The average number of pivot steps of the simplex-algorithm based on a generalized rotation-symmetry-model

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