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

DOI10.1007/s00186-014-0483-8zbMath1311.90070OpenAlexW2039742477MaRDI QIDQ486944

Karl Heinz Borgwardt, Markus Göhl

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 programmingprobabilistic analysisstochastic geometrysimplex methodaverage case analysisrotation symmetry model

Mathematics Subject Classification ID

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

Cites Work

• Average-case analysis of the double description method and the beneath-beyond algorithm
• 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
• The Average number of pivot steps required by the Simplex-Method is polynomial
• [https://portal.mardi4nfdi.de/wiki/Publication:5728818 �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten]
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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