TY - JOUR

T1 - Approximate kernel clustering

AU - Khot, Subhash

AU - Naor, Assaf

N1 - Funding Information:
Acknowledgements. We thank Alex Smola for bringing the problem of approximation algorithms for kernel clustering to our attention and for encouraging us to publish our results. Research supported in part by NSF Career award CCF-0643626, and a Microsoft New Faculty Fellowship. Research supported by NSF grants CCF-0635078 and DMS-0528387.

PY - 2009/1

Y1 - 2009/1

N2 - In the kernel clustering problem we are given a large n × n positive-semidefinite matrix A = (aij) with Σ i, j=1n aij = 0 and a small k × k positive-semidefinite matrix B = (bij). The goal is to find a partition S1, ⋯, Sk of {1, ⋯ n} which maximizes the quantity Σi, j=1k(Σ (p, q)εSi×Sj apq)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.

AB - In the kernel clustering problem we are given a large n × n positive-semidefinite matrix A = (aij) with Σ i, j=1n aij = 0 and a small k × k positive-semidefinite matrix B = (bij). The goal is to find a partition S1, ⋯, Sk of {1, ⋯ n} which maximizes the quantity Σi, j=1k(Σ (p, q)εSi×Sj apq)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.

UR - http://www.scopus.com/inward/record.url?scp=73949102599&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=73949102599&partnerID=8YFLogxK

U2 - 10.1112/S002557930000098X

DO - 10.1112/S002557930000098X

M3 - Article

AN - SCOPUS:73949102599

SN - 0025-5793

VL - 55

SP - 129

EP - 165

JO - Mathematika

JF - Mathematika

IS - 1-2

ER -