From Linear Separability to Unimodality: A Hierarchy of Pseudo-Boolean Functions

作     者：P. L. Hammer B. Simeone Th. M. Liebling D. de Werra 

出 版 物：《SIAM Journal on Discrete Mathematics》 

年 卷 期：1988年第1卷第2期

页      面：174-184页

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：05C pseudo-Boolean functions combinatorial optimization local improvement algorithms separability convexity unimodality 

摘      要：When an injective pseudo-Boolean function $f:B^n \to \mathbb{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 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.