Approximate kernel clustering

Subhash Khot, Assaf Naor

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