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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Parameterized Approximation Algorithm for the Diversity-Aware l-Centrum Problem

  • Junteng Song,
  • Shuilian Liu,
  • Yicheng Xu,
  • Yong Zhang

摘要

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.