Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.