论文标题
公平$ k $ -Median问题的新近似算法
New Approximation Algorithms for Fair $k$-median Problem
论文作者
论文摘要
公平的$ k $ -Median问题是重要的聚类问题之一。当前的最佳近似值为4.675，对于1-fair违规而言，这是Bercea等人提出的。 [大约2019年]。据我们所知，没有任何公平违规的问题没有可用的近似算法。在本文中，我们考虑了有界二倍指标和一般指标的公平$ k $ -Median问题。我们为公平$ k $ -Median问题提供了第一个QPTA，以加倍指标。基于双重指标的分裂树分解，我们提出了一个动态的编程过程，以找到候选中心，并应用最小成本的最大流量方法来处理客户的分配。特别是，为了克服公平限制造成的困难，我们构建了一个辅助图，并使用最小加权的完美匹配来获得一部分成本。对于一般指标中的公平$ k $ -Median问题，我们提出了一种带有比率$ o（\ log k）$的近似算法，该算法基于将给定空间嵌入树中的树指标和动态编程方法。我们针对公平$ k $ -Median问题的两种近似算法是相应问题的第一个结果，而没有任何公平违规。
The fair $k$-median problem is one of the important clustering problems. The current best approximation ratio is 4.675 for this problem with 1-fair violation, which was proposed by Bercea et al. [APPROX-RANDOM'2019]. As far as we know, there is no available approximation algorithm for the problem without any fair violation. In this paper, we consider the fair $k$-median problem in bounded doubling metrics and general metrics. We provide the first QPTAS for fair $k$-median problem in doubling metrics. Based on the split-tree decomposition of doubling metrics, we present a dynamic programming process to find the candidate centers, and apply min-cost max-flow method to deal with the assignment of clients. Especially, for overcoming the difficulties caused by the fair constraints, we construct an auxiliary graph and use minimum weighted perfect matching to get part of the cost. For the fair $k$-median problem in general metrics, we present an approximation algorithm with ratio $O(\log k)$, which is based on the embedding of given space into tree metrics, and the dynamic programming method. Our two approximation algorithms for the fair $k$-median problem are the first results for the corresponding problems without any fair violation, respectively.
