# Combinatorial Optimization and Relaxation

There are a number of NP-hard optimization problems that may be formulated as either binary linear or quadratic programs, i.e.

$\min_x c^tx$ s.t. $x \in K, x_i \in \{0,1\}$ or $\min_x x^t Q x$ s.t. $x \in K, x_i \in \{0,1\}$ where $K$ is some reasonably nice convex set, and the hardness of the problems is due to the binary constraint.

A heuristic for solving problems such as this is to \textit{relax} the problem in some way (possibly reformulating it first), solve the relaxed problem to get a solution $x^r$ that is not binary, and then mapping the solution $x^r$ into a binary $x$ which serves as the approximate solution to the original binary problem.

I have seen at least two different approaches to going from the relaxed solution to the binary solution:

1. Some sort of binary thresholding operation (i.e. equivalent to a projection of $x^r$ onto the set of binary vectors)
2. Something fancier, e.g. in http://www.informatik.uni-hamburg.de/ML/contents/people/luxburg/publications/Luxburg07_tutorial.pdf the authors discuss spectral clustering as a heuristic for solving a normalized cut problem. The last step here involves using the $k$-means algorithm, as simple thresholding is inadequate in this context.

I'd like to learn more about this last aspect of the relaxation approach to combinatorial optimization: recovering an approximate discrete solution from a solution to the relaxed problem. In particular, I am interested in situations where "naive" thresholding is inadequate. Can anyone suggest any papers on this?