## Abstract

In the kernel clustering problem we are given a (large) n × n symmetric positive semidefinite matrix A = (a_{ij}) with ∑^{n}_{i=1} ∑^{n}_{j=1} a_{ij}=0 and a (small) k × k symmetric positive semidefinite matrix B = (b_{ij}). The goal is to find a partition {S_{1},...,S_{k}} of {1,...n} which maximizes ∑^{k}_{i=1} ∑^{k}_{i=1} (∑_{(p,q)εSi×Sj} a_{pq})b_{ij}. 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 b_{ij} = 〈v_{i},v_{j}〉 is the Gram matrix representation of B for some v_{1},....,v_{k}εℝ^{k} then R(B) is the minimum radius of a Euclidean ball containing the points {v_{1},...,v_{k}}. The parameter C(B) is defined as the maximum over all measurable partitions {A_{1},...,A_{k}} of ℝ^{k-1} of the quantity ∑^{k}_{i=1} ∑^{k}_{j=1}n_{ij} 〈Z_{i}, Z_{j}〉where for iε{1,...,k} the vector Z_{i} ε ℝ^{k-1} is the Gaussian moment of A_{i}. We also show that for every ε > 0, achieving an approximation guarantee of is Unique Games hard.

Original language | English (US) |
---|---|

Pages (from-to) | 269-300 |

Number of pages | 32 |

Journal | Random Structures and Algorithms |

Volume | 42 |

Issue number | 3 |

DOIs | |

State | Published - May 2013 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics

## Keywords

- Approximation algorithms
- Semidefinite programming
- Unique Games hardness