Lower bounds for a subexponential optimization algorithm

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.