1
$\begingroup$

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))$ ?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Welcome to CS.SE! Can you edit the question to add some context? You use a bunch of symbols without defining any of them. Also, please edit the question to ask only one question. This site doesn't work well for multiple questions per question. Ask your first question, and then see what answers you get; based on the answers, you might then be able to answer your subsequent questions, or you might be in a better position to ask your second question at that time. Also, please show us what you've tried, what your thoughts are, what approaches you've considered and why you rejected them. $\endgroup$
    – D.W. ♦
    Commented Feb 3, 2016 at 2:38
  • $\begingroup$ I have reformatted the question. Hopefully this looks better! $\endgroup$
    – gradstudent
    Commented Feb 3, 2016 at 14:58

1 Answer 1

Reset to default
1
$\begingroup$

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)$.

Improve this answer
$\endgroup$
13
  • $\begingroup$ 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?) $\endgroup$
    – gradstudent
    Commented Feb 3, 2016 at 16:25
  • $\begingroup$ The claim is just wrong. You can't deduce it in general. Perhaps for these particular graphs, equality holds, but you can only deduce this by considering the actual graphs. $\endgroup$
    – Yuval Filmus
    Commented Feb 3, 2016 at 16:36
  • $\begingroup$ Can you have a look at the first line of section 4 of these notes, cs.cmu.edu/~anupamg/adv-approx/lecture16.pdf where it says, "We now focus on the second question — that of the algorithmic gap: Are there instances G where AlgGW (G) ≤ (αGW + )Opt(G) (for any constant epsilon)? Note that such instances would imply that Sdp(G) = Opt(G)" What do they mean? $\endgroup$
    – gradstudent
    Commented Feb 8, 2016 at 15:36
  • $\begingroup$ 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!..) $\endgroup$
    – gradstudent
    Commented Feb 8, 2016 at 15:47
  • $\begingroup$ For these graphs it so happens that SDP equals OPT. This requires proof, which you can probably find in the lecture notes. On the other hand, you lose a lot in the rounding. $\endgroup$
    – Yuval Filmus
    Commented Feb 8, 2016 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.