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 algorithm; NP-complete; pseudo-Boolean function; unimodular functions; unimax functions

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C09: Boolean programming

Related Items

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

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