Premium
Lower bounds for a subexponential optimization algorithm
Author(s) -
Matoušek Jiří
Publication year - 1994
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240050408
Subject(s) - permutation (music) , class (philosophy) , algorithm , upper and lower bounds , linear programming , mathematics , running time , computer science , mathematical optimization , artificial intelligence , mathematical analysis , physics , acoustics
Recently Sharir and Welzl 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. 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. © 1994 John Wiley & Sons, Inc.