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

Main titleRandomized simplex algorithms on Klee-Minty cubes
AuthorGärtner, Bernd
AuthorZiegler, Günter M.
InstitutionUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
No. of Pages17 S.
Series Freie Universität Berlin, Fachbereich Mathematik : Ser. B ; 94,13
Classification (DDC)004 Data processing and Computer science
AbstractWe 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.
Documents
pdf-Datei
If your browser can't open the file, please download the file first and then open it
 
FU DepartmentDepartment of Mathematics and Computer Science
Other affiliation(s)Institut für Informatik
Year of publication1994
Type of documentMaps
LanguageEnglish
Terms of use/Rights Nutzungsbedingungen
Created at2009-03-13 : 02:42:00
Last changed2014-01-23 : 04:21:15
 
Static URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001151
Statistics