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?
Grothendieck Constant of a graph and approximation limits
Turbo
- 13.9k
- 1
- 27
- 76