Sharp kernel clustering algorithms and their associated Grothendieck inequalities

Subhash Khot, Assaf Naor

In the kernel clustering problem we are given a (large) $n\times n$ symmetric positive semidefinite matrix $A=(a_{ij})$ with ${\sum }_{i=1}^n{\sum }_{j=1}^n{a}_{ij}=0$ and a (small) $k\ti…