A Continuous Approach to Compute an Upper Bound in a Quadratic Maximization Problem with Integer Constraints

In the graph partitioning problem, as in other NP-hard problems, the problem of proving the existence of a cut of given size is easy and can be accomplished by exhibiting a solution with the correct value. On the other hand proving the non-existence of a cut better than a given value is very difficult. We consider the problem of maximizing a quadratic function x sup T Q x where Q is a n x n real symmetric matrix with x an n- dimensional vector constrained to be an element of {-1, 1} sup n. In the paper we propose a technique for obtaining upper bounds on solutions to the problem using a continuous approach.