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

DOI10.1007/S00186-014-0483-8zbMATH Open1311.90070OpenAlexW2039742477MaRDI QIDQ486944FDOQ486944

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten
• The simplex method. A probabilistic analysis
• Erratum: ``A sharp upper bound for the expected number of shadow vertices in LP-polyhedra under orthogonal projection on two-dimensional planes
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Average number of pivot steps required by the Simplex-Method is polynomial
• Title not available (Why is that?)
• Average-case analysis of the double description method and the beneath-beyond algorithm

Cited In (4)

• 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
• 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)