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

• DOI: 10.1007/s10878-006-9625-0
• Publication Date: 2006-08-17T19:29:24Z
• Authors: Eranda Çela; Bettina Klinz; Christophe Meyer
• Keywords: 0102 computer and information sciences; 01 natural sciences

In this paper we consider the constant rank unconstrained quadratic 0-1 optimization problem, CR-QP01 for short. This problem consists in minimizing the quadratic function 〈x, Ax〉 + 〈c, x〉 over the set {0,1}n where c is a vector in ℝn and A is a symmetric real n × n matrix of constant rank r.