Recognition problems for special classes of polynomials in 0-1 variables

DOI10.1007/BF01587085zbMath0674.90069MaRDI QIDQ1121786

Yves Cramer

Publication date: 1989

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

polynomial algorithmNP-completepseudo-Boolean functionunimodular functionsunimax functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean programming (90C09)

Related Items

Extending shelling orders and a hierarchy of functions of unimodal simple polytopes, The Expressive Power of Binary Submodular Functions, A lower bound for a constrained quadratic \(0\)-\(1\) minimization problem, On the geometric separability of Boolean functions, Tractable Relaxations of Composite Functions, Classes of submodular constraints expressible by graph cuts, Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2, Explicit convex and concave envelopes through polyhedral subdivisions, Computing the value of the convex envelope of quadratic forms over polytopes through a semidefinite program, Complexity of uniqueness and local search in quadratic 0-1 programming, Tabu search-based metaheuristic algorithm for software system reliability problems, Polyhedral subdivisions and functional forms for the convex envelopes of bilinear, fractional and other bivariate functions over general polytopes, Concave extensions for nonlinear 0-1 maximization problems, The expressive power of binary submodular functions, Pseudo-Boolean optimization, Generalized roof duality, A cross entropy based algorithm for reliability problems, Global optimization of nonconvex problems with multilinear intermediates

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
• Unimodular functions
• On submodular function minimization
• The ellipsoid method and its consequences in combinatorial optimization
• On the supermodular knapsack problem
• Recognition of a class of unimodular functions
• Hill Climbing with Multiple Local Optima
• Minimum cuts, modular functions, and matroid polyhedra
• From Linear Separability to Unimodality: A Hierarchy of Pseudo-Boolean Functions
• Methods of Nonlinear 0-1 Programming
• Low order polynomial bounds on the expected performance of local improvement algorithms
• A note on the monotonicity of pseudo-Boolean functions
• Discrete optimization on a multivariable boolean lattice