# sparse binary vector

I want to know if the following problem has been solved

max_w w'Rw

where the entries of the vector w are binary (w_i= {0,1} )

-
where the matrix is positive semidefinite. Obviously, this problem is a NP-Hard combinatorial problem. My question is if this problem can be relaxed and somehow rewritten as a convex problem. Thanks –  Cruiselan Feb 15 '13 at 17:37
The statement of the question should be edited into the body of the question, not left in a comment. –  Gerry Myerson Feb 15 '13 at 22:06
search for "binary QP" or "boolean QP" and you'll find tons of info. –  Suvrit Feb 15 '13 at 23:54

• After a Cholesky factorization $R=T'T$, your problem becomes the maximization of the Euclidean norm over the parallelotope formed by the points $Tw$. This problem is discussed in H. L. Bodlaender, P. Gritzmann, V. Klee, J. van Leeuwen: Computational complexity of norm-maximization, Combinatorica 10 (1990), 203-225.