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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.