Unconstrained zero-one quadratic maximization problems can be solved in polynomial time when the symmetric matrix describing the objective function is positive semidefinite of fixed rank with known spectral decomposition.
Details
Title
A polynomial case of inconstrained zero-one queadratic optimization
