##
Lower Bounds for a Subexponential Optimization
Algorithm

###
Jiri Matousek
Department of Computer Science
Charles University, CSFR
Report B 92-15
July 92

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-92-15.ps.gz

Recently Sharir and Welzl \cite{ShWLp} 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 \cite{MSWsubex}.
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.