UNIVERSITÄTSBIBLIOTHEK

On the Variance of the Number of Pivot Steps Required by the Simplex Algorithm

  • Despite their very good empirical performance most of the simplex algorithm's variants require exponentially many pivot steps in terms of the problem dimensions of the given linear programming problem (LPP) in worst-case situtation. The first to explain the large gap between practical experience and the disappointing worst-case was Borgwardt (1982a,b), who could prove polynomiality on tbe average for a certain variant of the algorithm-the " Schatteneckenalgorithmus (shadow vertex algorithm)" - using a stochastic problem simulation.

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Karl-Heinz Küfer
URN (Permalink):urn:nbn:de:hbz:386-kluedo-48744
Schriftenreihe (Bandnummer):Preprints (rote Reihe) des Fachbereich Mathematik (238)
Dokumentart:Bericht
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):18.10.2017
Jahr der Veröffentlichung:1993
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):18.10.2017
Seitenzahl:12
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 510 Mathematik
Lizenz (Deutsch):Creative Commons 4.0 - Namensnennung, nicht kommerziell, keine Bearbeitung (CC BY-NC-ND 4.0)