2009/06/25 by Subhash Khot, Khot, Subhash, Assaf Naor +1 · 1 citation
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Sparse and Compressive Sensing Techniques #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.0906.4816
arxiv created 2009/06/25 · openalex publication_date 2009/06/25 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the kernel clustering problem we are given a (large) n× n symmetric positive semidefinite matrix A=(aij) with ∑i=1n∑j=1n aij=0 and a (small) k× k symmetric positive semidefinite matrix B=(bij). The goal is to find a partition \S1,...,Sk\ of \1,... n\ which maximizes ∑i=1k∑j=1k (∑(p,q)∈ Si× Sjapq)bij. We design a polynomial time approximation algorithm that achieves an approximation ratio of (R(B)2)/(C(B)), where R(B) and C(B) are geometric parameters that depend only on the matrix B, defined as follows: if bij = < vi, vj> is the Gram matrix representation of B for some v1,...,vk∈ \Rk then R(B) is the minimum radius of a Euclidean ball containing the points \v1, ..., vk\. The parameter C(B) is defined as the maximum over all measurable partitions \A1,...,Ak\ of \Rk-1 of the quantity ∑i=1k∑j=1k bij< zi,zj>, where for i∈ \1,...,k\ the vector zi∈ \Rk-1 is the Gaussian moment of Ai, i.e., zi=\frac1(2π)(k-1)/2∫Aixe-‖x‖22/2dx. We also show that for every \eps > 0, achieving an approximation guarantee of (1-\e)(R(B)2)/(C(B)) is Unique Games hard.