1
$\begingroup$

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?

$\endgroup$

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.