3
$\begingroup$

My question is: given a maxcut instance, if it costs too much to solve it to optimal practically but we can get an optimal solution of SDP relaxation quickly, can we assess the quality of this SDP solution? (like estimate the OPT/SDP ratio for THIS INSTANCE). My preliminary thought is that if the rank of the SDP solution (matrix) is far bigger than 1, then SDP relaxation is probably not good for this instance. But can we say for sure? Is there some literature that can be pointed to?

In Goemans and Williamson 1995 paper "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming", they asserted $\text{SDP} \ge \text{OPT} \ge \text{ALG} \ge 0.878 \text{ SDP}$. In Feige and Schechtman 2002 paper "On the optimality of the random hyperplane rounding technique for max cut", they constructed maxcut instances that $\text{OPT} \le (0.878 + \varepsilon) \text{ SDP}$. However, both of these are worst case analysis. My question is practically assessing the quality of SDP relaxation for a particular maxcut instance without knowing the optimum to the original problem.

In reading ""An Optimal SDP Algorithm for Max-Cut, and Equally Optimal Long Code Tests" by R.O'Donnell etc. from Stoc'08, the author gave a curve of $\text{OPT} vs. \text{SDP}$. So the worst-case analysis of $\frac{\text{OPT}}{\text{SDP}}$ is solved. However I have difficulty in understanding their proof so I don't know whether their work can be helpful to this problem.

$\endgroup$
  • $\begingroup$ By "solution" do you mean an "optimal solution"? $\endgroup$ – Yoshio Okamoto Aug 23 '11 at 4:58
  • $\begingroup$ Yes. A "sdp solution" in my original post means optimal solution to the SDP formulation (numerically). $\endgroup$ – Ben Aug 23 '11 at 8:55
  • 1
    $\begingroup$ Thanks for the clarification. If you look at the Goemans-Williamson paper, you should find an experimental section that explains how they assess the quality by "integrality gap". I would guess that's what you want, but I could be wrong. $\endgroup$ – Yoshio Okamoto Aug 23 '11 at 15:17

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.