Technical Report 2002-018

Optimization on Completely Unimodal Hypercubes

Henrik Björklund, Sven Sandberg, and Sergei Vorobyov

May 2002


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(20.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(20.46n) = O(1.376n) upper bound for the Random Multiple Switches Algorithm with Random Sampling.

We also show how Kalai-Ludwig's algorithm for Simple Stochastic Games [Ludwig95] can be modified to solve the problem at hand, and that the modified algorithm preserves the subexponential, 2O(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.

Available as compressed Postscript (339 kB) and Postscript (943 kB)

Download BibTeX entry.