Dokumentenserver der Freien Universität Berlin

Objekt-Metadaten

Randomized simplex algorithms on Klee-Minty cubes
Gärtner, Bernd ;  Ziegler, Günter M. ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

HaupttitelRandomized simplex algorithms on Klee-Minty cubes
AutorGärtner, Bernd
AutorZiegler, Günter M.
Institution/KörperschaftUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
Seitenzahl17 S.
Schriftenreihe Freie Universität Berlin, Fachbereich Mathematik : Ser. B ; 94,13
DDC004 Datenverarbeitung; Informatik
ZusammenfassungWe investigate the behavior of randomized simplex algorithms on special linear programs. For this, we develop combinatorial models for the Klee-Minty cubes [17] and similar linear programs with exponential decreasing paths. The analysis of two most natural randomized pivot rules on the Klee-Minty cubes leads to (nearly) quadratic lower bounds for the complexity of linear programming with random pivots. Thus, we disprove two bounds conjectured in the literature. At the same time, we establish quadratic upper bounds for random pivots on the linear programs under investigation. This motivates the question whether some randomized pivot rules possibly have quadratic worst-case behavior on general linear programs.
Dokumente
pdf-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
 
Fachbereich/EinrichtungFB Mathematik und Informatik
Arbeitsbereich/InstitutInstitut für Informatik
Erscheinungsjahr1994
Dokumententyp/-SammlungenKarten
SpracheEnglisch
Rechte Nutzungsbedingungen
Erstellt am13.03.2009 - 14:42:00
Letzte Änderung23.01.2014 - 16:21:15
 
Statische URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001151
Zugriffsstatistik