Approximate kernel clustering

In the kernel clustering problem we are given a large n × n positive-semidefinite matrix A = (a_ij) with Σ _{i, j=1}ⁿ a_ij = 0 and a small k × k positive-semidefinite matrix B = (b_ij). The goal is to find a partition S₁, ⋯, S_k of {1, ⋯ n} which maximizes the quantity Σ_{i, j=1}^k(Σ _{(p, q)}εS_i×S_j a_pq)b _ij. We study the computational complexity of this generic clustering problem which originates in the theory of machine learning. We design a constant factor polynomial time approximation algorithm for this problem, answering a question posed by Song et al. In some cases we manage to compute the sharp approximation threshold for this problem assuming the unique games conjecture (UGC). In particular, when B is the 3 × 3 identity matrix the UGC hardness threshold of this problem is exactly 16π/27. We present and study a geometric conjecture of independent interest which we show would imply that the UGC threshold when B is the k × k identity matrix is (8π/9)(1 - 1/k) for every k ≥ 3.