From linear separability to unimodality: a hierarchy of pseudo-boolean functions

When an injective pseudo-Boolean function f:B^n -> R is minimized, where B^n=0,1^n is the set of vertices of the unit-hypercube, it is natural to consider so-called greedy vertex-following algorithms. These algorithms construct a sequence of neighbouring (Hamming distance 1) vertices with decreasing f-value. The question arises as to when such algorithm will find the global optimum given any starting point. This paper describes a hierarchy of such classes of fonctions that are shown to strictly contain each other. These classes are, in increasing order of generality, the threshold, the saddle-free, the pseudomodular, the completely unimodal, the unimodal, and the unimin (respectively, unimax) functions. Some considerations as to the complexity of the above-mentioned class of algorithm are also made.

Published in:
SIAM Journal on Discrete Mathematics, 1, 2, 174-184
PRO 88.01

 Record created 2006-02-13, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)