Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem |
| |
Authors: | Eranda Çela Bettina Klinz Christophe Meyer |
| |
Institution: | 1. Institut für Optimierung und Diskrete Mathematik, Technische Universit?t Graz, Steyrergasse 30, A-8010, Graz, Austria 2. Département d’Informatique et de Recherche Opérationnelle, Université de Montréal, C.P. 6128, succ. Centre-ville, Montréal, (Québec), H3C 3J7, Canada
|
| |
Abstract: | 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.
We first present a pseudo-polynomial algorithm for solving the problem CR-QP01, which is known to be NP-hard already for r = 1. 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 A. Finally we compare our algorithm with the algorithm of Allemand et al. (2001) for the CR-QP01 with negative semidefinite A 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. |
| |
Keywords: | Quadratic 0-1 programming Special case Local minima Constant rank matrix Stable sets |
本文献已被 SpringerLink 等数据库收录! |
|