A Parameterized Approximation Algorithm for the Diversity-Aware l-Centrum Problem
摘要
We propose and study a combination model of l-centrum and the diversity-aware k-median problem, called the diversity-aware l-centrum problem. In this problem, we are given a set of clients, a set of facilities in a metric space, integers k and l, and r[i] \((i\in [t])\) for each facility group. The diversity constraint refers to the requirement that each group must contain at least r[i] open facilities. The goal is to find a subset of facilities of size at most k so as to minimize the sum of the l largest distances from a client to its nearest open facility while satisfying the diversity constraint. As our main contribution, this work provides the first constant approximation algorithm for the diversity-aware l-centrum problem in FPT time, based on a combination of leader selection and coreset construction techniques.