Navigation/Menü: Links auf weitere Seiten dieser Website
Objekt-Metadaten
| Lower bounds for a subexponential optimization algorithm Matoušek, Jiří |
| Haupttitel | Lower bounds for a subexponential optimization algorithm |
| Autor | Matoušek, Jiří |
| Seitenzahl | 18 S. |
| Schriftenreihe | Freie Universität Berlin, Fachbereich Mathematik : Ser. B ; 92,15 |
| Fachbereich/Einrichtung | FB Mathematik und Informatik |
| Arbeitsbereich/Institut | Institut für Informatik |
| Erscheinungsjahr | 1992 |
| Dokumente | pdf-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
|
| DDC | 004 Datenverarbeitung; Informatik |
| Dokumententyp/-Sammlungen | Report |
| Medientyp/Format | Text |
| Abstract | Recently 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. |
| Sprache | Englisch |
| Rechte | Nutzungsbedingungen |
| Zugriffstatistik | |
| Statische URL | http://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001008 |
| Erstellt am | 10.03.2009 - 15:11:27 |
| Letzte Änderung | 04.04.2013 - 09:33:23 |
