Recognition problems for special classes of polynomials in 0-1 variables
From MaRDI portal
The following decision problem P is considered. Given a pseudo-Boolean function f in polynomial form and a class C of pseudo-Boolean functions, is f not in C? For the classes of monotonic, supermodular, threshold, completely unimodular, and unimax functions it is shown that P is NP- complete. In each case there is a reduction from the partition problem to P. For the class of unimodular functions a polynomial algorithm is presented which solves P.
Recommendations
- On a Special Class of Polynomials
- On some special polynomials
- A polynomial recognition of unit forms
- On a problem in the theory of polynomials
- scientific article; zbMATH DE number 3875705
- scientific article; zbMATH DE number 3353355
- Polynomials of certain special types
- scientific article; zbMATH DE number 841129
- Certain extremal problems for polynomials
- ON THE ZEROS OF RECURSIVELY DEFINED POLYNOMIALS
Cites work
- A new polynomial-time algorithm for linear programming
- A note on the monotonicity of pseudo-Boolean functions
- Discrete optimization on a multivariable boolean lattice
- From Linear Separability to Unimodality: A Hierarchy of Pseudo-Boolean Functions
- Hill Climbing with Multiple Local Optima
- scientific article; zbMATH DE number 3904328 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3641502 (Why is no real title available?)
- scientific article; zbMATH DE number 3249560 (Why is no real title available?)
- Low order polynomial bounds on the expected performance of local improvement algorithms
- Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
- Methods of Nonlinear 0-1 Programming
- Minimum cuts, modular functions, and matroid polyhedra
- On submodular function minimization
- On the supermodular knapsack problem
- Recognition of a class of unimodular functions
- The ellipsoid method and its consequences in combinatorial optimization
- Unimodular functions
Cited in
(26)- A cross entropy based algorithm for reliability problems
- Unimodular functions
- 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
- Recognition of a class of unimodular functions
- Recognizing ℙnin Classical and Modern Setting
- Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2
- The Expressive Power of Binary Submodular Functions
- scientific article; zbMATH DE number 1182572 (Why is no real title available?)
- Tractable relaxations of composite functions
- 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
- MIP relaxations in factorable programming
- A linear-time algorithm to compute the conjugate of nonconvex bivariate piecewise linear-quadratic functions
- Concave extensions for nonlinear 0-1 maximization problems
- The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization
- Pseudo-Boolean optimization
- Generalized roof duality
- Computing the convex envelope of bivariate piecewise linear-quadratic functions in linear time
- Tabu search-based metaheuristic algorithm for software system reliability problems
- The expressive power of binary submodular functions
This page was built for publication: Recognition problems for special classes of polynomials in 0-1 variables
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1121786)
