Polynomially Solvable Cases of Binary Quadratic Programs

DOI10.1007/978-0-387-89496-6_11zbMath1231.90324OpenAlexW2143406968MaRDI QIDQ3059290

Xiaoling Sun, Chunli Liu, Li, Duan, Shenshen Gu, Jian-Jun 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

zbMATH Keywords

SDP relaxationseries-parallel graphpolynomial solvabilitybinary quadratic programlogic circuit, Lagrangian dual

Mathematics Subject Classification ID

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

Related Items

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

Uses Software

• Biq Mac