@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. }
}