A solvable class of quadratic 0-1 programming

DOI10.1016/0166-218X(92)90256-AzbMath0771.90071MaRDI QIDQ1193723

Michael L. Bushnell, Srimat T. Chakradhar

Publication date: 27 September 1992

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-completelogic circuitpseudo-Boolean quadratic function

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20) Boolean programming (90C09) Boolean functions (06E30)

Related Items

Complexity and Polynomially Solvable Special Cases of QUBO ⋮ On duality gap in binary quadratic programming ⋮ A polynomial case of convex integer quadratic programming problems with box integer constraints ⋮ Parametric Lagrangian dual for the binary quadratic programming problem ⋮ QUAD01: A data-structured implementation of Hansen's quadratic zero-one programming algorithm ⋮ Simulated annealing for the unconstrained quadratic pseudo-Boolean function ⋮ Closed-form formulas for evaluating \(r\)-flip moves to the unconstrained binary quadratic programming problem

Cites Work

• The indefinite zero-one quadratic problem
• A solvable case of quadratic 0-1 programming
• Polytope des independants d'un graphe série-parallèle
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• Minimum cuts and related problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item