About showing algorithmic gap instance for the Goemans-Williamson SDP

Using usual notation we have,

$SDP(G) \geq OPT(G) \geq Alg_{GW}(G) \geq \alpha_{GW} SDP(G) \geq \alpha_{GW} OPT(G)$

where we mean,

$SDP(G)$ = The maximum value that the SDP finds of the objective function $\sum_{(u,v) \in E} w_{uv}( 1-\vec{y_u}.\vec{y_v})/2$ (one unit vector $\vec{y_v}$ in $\mathbb{R}^d$ for each vertex $v$ for some $d$) And $w_{uv}$ are the given edge weights such that $\sum_{(u,v) \in E} w_{uv} =1$

$OPT(G)$ = The actual size of the max-cut for the graph

$Alg_{GW}(G)$ = The value of the max-cut returned by the randomized rounding prescription of Goemans-Williamson

$\alpha_{GW}$ = the famous constant of $\sim 0.878$

• If say someone shows that for every $\epsilon$ there is a graph $G(\epsilon)$ such that $(\alpha_{GW}+\epsilon)OPT(G(\epsilon)) \geq Alg_{GW}(G(\epsilon))$ then does this imply that this is a class of graphs on which the algorithm is performing as bad as it could?

• Why does showing the existence of such a family of graphs as above also necessarily imply that on this family $SDP(G(\epsilon)) = OPT(G(\epsilon))$ ?

A graph for which $Alg(G) = \beta OPT(G)$ is, by definition, a graph on which the algorithm has approximation ratio $\beta$. You can use this insight to answer the first question.
As to your second question, suppose that $Alg(G) \leq (\alpha_{GW}+\epsilon) OPT(G)$. Since $Alg(G) \geq \alpha_{GW} SDP(G)$, we deduce that $$\alpha_{GW} SDP(G) \leq Alg(G) \leq (\alpha_{GW}+\epsilon) OPT(G).$$ Therefore $SDP(G) \leq (1+O(\epsilon)) OPT(G)$.
• Yes. This I understand. But I am not able to see the equivalence between showing that (1) for this set of graphs it is always true that $SDP(G) \leq (1+O(\epsilon) )OPT(G)$ for all $\epsilon$ and (2) the claim that $SDP$ and $OPT$ match on this set. Aren't these two things different? (except that if someone also shows that there really does exist a graph precisely at $\epsilon = 0$ then only for that graph I would think that one can legitimately say that SDP and OPT match. right?) – gradstudent Feb 3 '16 at 16:25
• Like, they start off trying to show that there exists a family of graphs for which, $\alpha_{GW} SDP(G) \leq Alg(G) \leq (\alpha_{GW}+\epsilon) OPT(G)$ but they say that for this same class of graphs $SDP = OPT = Obj$! If all these 3 quantities are coinciding then how is this class of graphs the "worst" case for GW? (as they set out to show initially!) (..infact for this class Obj = OPT always and hence there seems to be nothing for the SDP to optimize!..) – gradstudent Feb 8 '16 at 15:47