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

Main titleLower bounds for a subexponential optimization algorithm
AuthorMatoušek, Jiří
InstitutionUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
No. of Pages18 S.
Series Freie Universität Berlin, Fachbereich Mathematik : Ser. B ; 92,15
Classification (DDC)004 Data processing and Computer science
AbstractRecently 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.
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 publication1992
Type of documentWorking paper
Terms of use/Rights Nutzungsbedingungen
Created at2009-03-10 : 02:11:27
Last changed2015-03-25 : 06:43:17
Static URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001008