Polynomially solvable cases of binary quadratic programs

DOI10.1007/978-0-387-89496-6_11zbMATH Open1231.90324OpenAlexW2143406968MaRDI QIDQ3059290FDOQ3059290

Authors: Duan Li, Xiaoling Sun, Shenshen Gu, C. L. Liu, J. J. Gao 

Publication date: 8 December 2010

Published in: Springer Optimization and Its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-0-387-89496-6_11

Recommendations

• The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases
• A solvable class of quadratic 0-1 programming
• scientific article; zbMATH DE number 1139465
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem

zbMATH Keywords

polynomial solvabilitySDP relaxationseries-parallel graphbinary quadratic programlogic circuit, Lagrangian dual

Mathematics Subject Classification ID

Quadratic programming (90C20) Combinatorial optimization (90C27) Boolean programming (90C09)

Cited In (8)

• Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach
• Distributed resource allocation with binary decisions via Newton-like neural network dynamics
• The generalized vertex cover problem and some variations
• Complexity and polynomially solvable special cases of QUBO
• A polynomial case of convex integer quadratic programming problems with box integer constraints
• On duality gap in binary quadratic programming
• Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem
• The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases

Uses Software

• Biq Mac

This page was built for publication: Polynomially solvable cases of binary quadratic programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3059290)