Lower bounds for a subexponential optimization algorithm

摘要: Recently Sharir and Welzl described a randomized algorithm for certain class of optimization problems (including linear programming), then subexponential bound the expected running time was established. We give an example (artificial) problem fitting into Sharir–Welzl framework which is close to upper bound, thus showing that analysis cannot be much improved without stronger assumptions on and/or modifying algorithm. Further we describe results computer simulations specific programming problem, indicate “one‐permutation” “move‐to‐front” variants may sometimes perform worse than itself. © 1994 John Wiley & Sons, Inc.