<p>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?</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-08-23T04:58:30.557Z
By "solution" do you mean an "optimal solution"?
Yoshio Okamoto
CC BY-SA 3.0
2011-08-23T08:55:18.400Z
Yes. A "sdp solution" in my original post means optimal solution to the SDP formulation (numerically).
Ben
CC BY-SA 3.0
2011-08-23T15:17:16.687Z
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.
Yoshio Okamoto
<ds.algorithms><semidefinite-programming><max-cut>
The Quality of SDP relaxation on MaxCut
Ben
# The Quality of SDP relaxation on MaxCut

(Asked by: username_0 on 2011-08-22)

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.

**Tags:** ds.algorithms, semidefinite-programming, max-cut
> **Comments:**
> **username_1**: By "solution" do you mean an "optimal solution"?  
> **username_0**: Yes. A "sdp solution" in my original post means optimal solution to the SDP formulation (numerically).  
> **username_1**: 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.  

---

## 0 answers

