优先级k-中心问题的FPT近似算法  

An FPT approximation algorithm for the priority k-center problem

作　　者：冯启龙[1,2] 龙睿 吴小良 仲文明 FENG Qilong;LONG Rui;WU Xiaoliang;ZHONG Wenming(School of Computer Science and Engineering,Central South University,Changsha 410083,China;Xiangjiang Laboratory,Changsha 410205,China;School of Foreign Languages,Central South University,Changsha 410083,China)

机构地区：[1]中南大学计算机学院,湖南长沙410083 [2]湘江实验室,湖南长沙410205 [3]中南大学外国语学院,湖南长沙410083

出　　处：《中南大学学报（自然科学版）》2023年第7期2718-2724,共7页Journal of Central South University:Science and Technology

基　　金：国家自然科学基金资助项目(62172446);湘江实验室开放项目(22XJ02002);中南大学前沿交叉研究项目(2023QYJC023)。

摘　　要：优先级k-中心问题是聚类领域中1个经典的NP-难问题。给定度量空间中的1个集合X和参数k∈N+,其中,集合X中每个点v都被赋予1个优先级参数r(v)∈R+,求解1个大小为k的子集S■X,考虑集合X中任意数据点到集合S的距离与r(v)之间比值,找到最大比值,目标是最小化该比值。对于优先级k-中心问题,目前最好的结近似算法是多项式时间内的2-近似算法,该问题不存在1个(2-ε)-近似算法,(其中,ε为用于控制算法近似比的参数)。本文研究优先级k-中心问题的固定参数可解(fixed-parameter tractability,FPT)时间内的近似算法。基于k-中心问题的贪心策略,提出新的中心点选取方法。研究结果表明:该方法通过贪心策略选取一定规模的候选中心点集,利用加倍度量维度的性质去限制该集合的大小,实现了FPT时间内的(1+ε)-近似算法,降低了目前该问题的近似比。The priority k-center problem is a classical NP-hard problem in clustering.A set X of points in a metric space and a parameter k∈N+were given where each point v∈X was entitled to a priority parameter r(v)∈R+,the goal was to find a subset SÍX with size k such that the maximum ratio between any point to its closest center in S and its priority parameter r(v)was minimized.For the priority k-center problem,the known best result is a 2-approximation in polynomial time and there exists no a(2-ϵ)-approximation algorithm for this problem(whereϵis a parameter used to control the approximation ratio of algorithm).In this paper,the FPT approximation algorithm for the priority k-center problem was studied.Based on the greedy strategy used for the k-center problem,a new selection method was presented for centers.By using the greedy strategy,the method selects a set of candidate centers where the size can be upper bounded by the property of the doubling dimension,a(1+ϵ)-approximation in FPT time is achieved,and the known approximation ratio of this problem can be reduced.

关 键 词：近似算法 FPT近似算法 优先级k-中心问题 k-中心问题 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]