G-2006-36
Polynomially Solvable Cases of the Constant Rank Unconstrained Quadratic 0-1 Programming Problem
, , and BibTeX reference
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
over the set where is a vector in and is a
symmetric real matrix of constant rank .
We first present a pseudo-polynomial algorithm for solving the problem CR-QP01,
which is known to be NP-hard already for . We then derive two new classes of
special cases of the CR-QP01 which can be solved in polynomial time. These classes
result from further restrictions on the matrix . Finally we compare our algorithm with
the algorithm of Allemand et al. (2001) for the CR-QP01 with negative semidefinite
and extend the range of applicability of the latter algorithm. It turns out that neither
of the two algorithms dominates the other with respect to the class of instances which
can be solved in polynomial time.
Published May 2006 , 36 pages
Document
G-2006-36.pdf (300 KB)