Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem

DOI10.1007/s10878-006-9625-0zbMath1255.90081OpenAlexW2074049387MaRDI QIDQ2369979

Bettina Klinz, Christophe Meyer, Eranda Çela

Publication date: 21 June 2007

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-006-9625-0

zbMATH Keywords

local minimaquadratic 0-1 programmingstable setsspecial caseconstant rank matrix

Mathematics Subject Classification ID

Quadratic programming (90C20) Boolean programming (90C09)

Related Items

A Polytope for a Product of Real Linear Functions in 0/1 Variables, Complexity and Polynomially Solvable Special Cases of QUBO, The Bipartite QUBO, The Boolean quadratic programming problem with generalized upper bound constraints, A polynomial-time recursive algorithm for some unconstrained quadratic optimization problems, On duality gap in binary quadratic programming, Parametric Lagrangian dual for the binary quadratic programming problem, Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems, The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases

Uses Software

• Algorithm 457

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A solvable case of quadratic 0-1 programming
• On generating all maximal independent sets
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• A partial k-arboretum of graphs with bounded treewidth
• Biplanar graphs: A survey
• Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm
• The basic algorithm for pseudo-Boolean programming revisited
• Graph separation techniques for quadratic zero-one programming
• Maximizing the Product of Two Linear Functions In 0-1 Variables
• Arboricity and Subgraph Listing Algorithms
• On the complexity of integer programming
• Minimum cuts and related problems
• A New Algorithm for Generating All the Maximal Independent Sets
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Corrections to Bierstone's Algorithm for Generating Cliques
• Algorithm 457: finding all cliques of an undirected graph
• LATIN 2004: Theoretical Informatics
• A polynomial case of unconstrained zero-one quadratic optimization