## Abstract

We consider the classical κ-means clustering problem in the setting of bi-criteria approximation, in which an algorithm is allowed to output βκ > k clusters, and must produce a clustering with cost at most α times the to the cost of the optimal set of k clusters. We argue that this approach is natural in many settings, for which the exact number of clusters is a priori unknown, or unimportant up to a constant factor. We give new bi-criteria approximation algorithms, based on linear programming and local search, respectively, which attain a guarantee α(β) depending on the number κ of clusters that may be opened. Our guarantee α(β) is always at most 9+ϵ and improves rapidly with β (for example: α(2) < 2.59, and α(3) < 1.4). Moreover, our algorithms have only polynomial dependence on the dimension of the input data, and so are applicable in high-dimensional settings.

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

Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016 |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Volume | 60 |

ISBN (Electronic) | 9783959770187 |

DOIs | |

State | Published - Sep 1 2016 |

Event | 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016 - Paris, France Duration: Sep 7 2016 → Sep 9 2016 |

### Other

Other | 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016 |
---|---|

Country | France |

City | Paris |

Period | 9/7/16 → 9/9/16 |

## Keywords

- Bicriteria approximation algorithms
- Linear programming
- Local search
- κ-means clustering

## ASJC Scopus subject areas

- Software