1
$\begingroup$

Let $K(G)$ be the Grothendieck constant of a graph with adjacency matrix $A$. How is $K(G)$ precisely related to approximation limits for some standard NP complete problems such as Chromatic, Independence and Clique number approximation?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Do you know the survey arxiv.org/abs/1108.2464 by Khot and Naor? It seems that you should find answers to your question there. $\endgroup$
    – Mikael de la Salle
    Commented Jul 12, 2012 at 8:01
  • $\begingroup$ This is a good reference. Thankyou. $\endgroup$
    – Turbo
    Commented Jul 12, 2012 at 8:03

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .