Dokumentenserver der Freien Universität Berlin

Objekt-Metadaten

Lower bounds for a subexponential optimization algorithm
Matoušek, Jiří ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

HaupttitelLower bounds for a subexponential optimization algorithm
AutorMatoušek, Jiří
Institution/KörperschaftUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
Seitenzahl18 S.
Schriftenreihe Freie Universität Berlin, Fachbereich Mathematik : Ser. B ; 92,15
DDC004 Datenverarbeitung; Informatik
ZusammenfassungRecently Sharir and Welzl [SW92] described a randomized algorithm for a certain class of optimization problems (including linear programming), and then a subexponential bound for the expected running time was established [MSW92]. We give an example of an (artificial) optimization problem fitting into the Sharir-Welzl framework for which the running time is close to the upper bound, thus showing that the analysis of the algorithm cannot be much improved without stronger assumptions on the optimization problem and/or modifying the algorithm. Further we describe results of computer simulations for a specific linear programming problem, which indicate that "one-permutation'' and "move-to-front'' variants of the Sharir-Welzl algorithm may sometimes perform much worse than the algorithm itself.
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
Erscheinungsjahr1992
Dokumententyp/-SammlungenKarten
SpracheEnglisch
Rechte Nutzungsbedingungen
Erstellt am10.03.2009 - 14:11:27
Letzte Änderung23.01.2014 - 16:21:12
 
Statische URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001008
Zugriffsstatistik