Google Research

To Close Is Easier Than To Open: Dual Parameterization To k-Median

  • Jaroslaw Byrka
  • Szymon Dudycz
  • Pasin Manurangsi
  • Jan Marcinkowski
  • Michal Wlodarczyk
Workshop on Approximation and Online Algorithms (WAOA) (2020), pp. 113-126


The k-Median problem is one of the well-known optimization problems that formalizes the task of data clustering. Here, we are given sets of facilities F and clients C, and the goal is to open k facilities from the set F, which provides the best division into clusters, that is, the sum of distances from each client to the closest open facility is minimized. In the Capacitated k-Median, the facilities are also assigned capacities specifying how many clients can be served by each facility.

Both problems have been extensively studied from the perspective of approximation algorithms. Recently, several surprising results have come from the area of parameterized complexity, which provided better approximation factors via algorithms with running times of the form f(k) · poly(n). In this work, we extend this line of research by studying a different choice of parameterization. We consider the parameter l = |F| − k, that is, the number of facilities that remain closed. It turns out that such a parameterization reveals yet another behaviour of k-Median. We observe that the problem is W[1]-hard but it admits a parameterized approximation scheme. Namely, we present an algorithm with running time 2^O(l · log(l/ε)) · poly(n) that achieves(1 + ε)-approximation. On the other hand, we show that under the assumption of Gap Exponential Time Hypothesis, one cannot extend this result to the capacitated version of the problem.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work