In this setting, we survey several randomized optimization algorithms appropriate for CU-, CLG-, and RLG-functions. We show that the subexponential algorithms for linear programming by Kalai and Matousek, Sharir, and Welzl, can be adapted to optimizing the functions we study, with preserved subexponential expected running time. We examine the relations to two other abstract frameworks for subexponential optimization, the LP-type problems of Matousek, Sharir, Welzl, and the abstract optimization problems of G\"artner. The applicability of our abstract optimization approach to parity games builds upon a discrete strategy evaluation measure.
We also consider local search type algorithms, and settle two
nontrivial, but still exponential, upper bounds. As applications we
address some complexity-theoretic issues including
non-PLS-completeness of the problems studied.
Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-09.ps.gz