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?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
1
|
|
||||||||
|
