Vincent Cohen-Added: On the Parameterized Complexity of Various Clustering Problems

Talks on Frontiers of Parameterized Complexity

Keywords: Clustering, Parameterized Approximation

May 14, 2020
Vincent Cohen-Added, Google Zurich
Title: On the Parameterized Complexity of Various Clustering Problems

Abstract: Clustering problems are fundamental computational problems. On the one hand they are at the heart of various data analysis, bioinformatics or machine learning approaches, on the other hand, they can be seen as variants of 'set cover' problems (involving e.g. metrics, graphs with a special structure, etc.) and so are very basic problems.

For many applications, finding efficient fixed-parameter algorithms is a very natural approach. Popular choices of parameters are either parameters of the problem itself (e.g. the number of clusters) or on the underlying structure of the input (e.g. the dimension in the metric case). We will focus on classic metric clustering objectives such as k-median and k-means and review recent results on the fixed parameter complexity of these problems, and the most important open problems.