Uppsala University Department of Information Technology
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.