@TechReport{ it:2002-018,
author = {Henrik Bj{\"o}rklund and Sven Sandberg and Sergei
Vorobyov},
title = {Optimization on Completely Unimodal Hypercubes},
institution = {Department of Information Technology, Uppsala University},
department = {Computing Science Division},
year = {2002},
number = {2002-018},
month = may,
abstract = {We investigate and compare, both theoretically and
practically, several old and new algorithms for the
completely unimodal pseudo-boolean function optimization
problem. We settle the first nontrivial upper bounds for
two well-known local search algorithms, the Random and the
Greedy Single Switch algorithms. We also present the new
Random Multiple and All Profitable Switches algorithms.
These are not local search-type algorithms, and have not
been previously considered for this problem. We justify the
algorithms and show nontrivial upper bounds. In particular
we prove a $O(2^{0.775n})$ bound for the Random Multiple
Switches Algorithm, and also use random sampling to improve
the bounds for all above algorithms. In particular we give
a $O(2^{0.46n}) = O(1.376^n)$ upper bound for the Random
Multiple Switches Algorithm with Random Sampling.
We also show how Kalai-Ludwig's algorithm for Simple
Stochastic Games \cite{Ludwig95} can be modified to solve
the problem at hand, and that the modified algorithm
preserves the subexponential, $2^{O(\sqrt{n})}$, running
time.
We introduce and justify a new method for random generation
of `presumably hard' completely unimodal pseudo-boolean
functions. We also present experimental results indicating
that all the above algorithms perform well in practice. The
experiments, surprisingly, show that in all generated
example cases, the subexponential Kalai-Ludwig's algorithm
is outperformed by all the other algorithms. }
}