From linear separability to unimodality: A hierarchy of pseudo-Boolean functions

From linear separability to unimodality: A hierarchy of pseudo-Boolean functions

0.00 Avg rating0 Votes
Article ID: iaor19881117
Country: United States
Volume: 1
Issue: 2
Start Page Number: 174
End Page Number: 184
Publication Date: May 1988
Journal: SIAM Journal On Discrete Mathematics
Authors: , , ,
Abstract:

When an injective pseudo-Boolean function f:Bn⇒&λτ;∼ is minimized, where Bn={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 algorithms will find the global optimum given any starting point. This paper describes a hierarchy of such classes of functions 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 algorithms are also made.

Reviews

Required fields are marked *. Your email address will not be published.