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

DOI10.1137/0401019zbMath0668.05061OpenAlexW2088929609MaRDI QIDQ3820646

Dominique de Werra, Peter L. Hammer, Thomas M. Liebling, Bruno Simeone

Publication date: 1988

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0401019

zbMATH Keywords

convexitycombinatorial optimizationseparabilityunimodalitypseudo-Boolean functiongreedy vertex-following algorithmslocal improvement algorithms

Mathematics Subject Classification ID

Boolean functions (06E30) Graph theory (05C99)

Related Items

On anonymous and weighted voting systems, Extending shelling orders and a hierarchy of functions of unimodal simple polytopes, The worst case behavior of a greedy algorithm for a class of pseudo- Boolean functions, Recognition problems for special classes of polynomials in 0-1 variables, Lyapunov-Based Stability and Construction of Lyapunov Functions for Boolean Networks, Cyclic games and linear programming, Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm, On the \(k\)-systems of a simple polytope, Combinatorial structure and randomized subexponential algorithms for infinite games