MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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} )

share|cite|improve this question
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
up vote 1 down vote accepted
  • 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.
  • If your matrix is just symmetric, not necessarily p.s.d., then it is essentially the maximum cut problem. For this problem, there are (famous) convex relaxations, using for example semidefinite programming.
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.