An approximation algorithm for lower-bounded k-median with constant factor  

作　　者：Xiaoliang WU Feng SHI Yutian GUO Zhen ZHANG Junyu HUANG Jianxin WANG 

机构地区：[1]School of Computer Science and Engineering,Central South University,Changsha 410083,China [2]Hunan Provincial Key Lab on Bioinformatics,Central South University,Changsha 410083,China [3]School of Frontier Crossover Studies,Hunan University of Technology and Business,Changsha 410083,China

出　　处：《Science China(Information Sciences)》2022年第4期89-97,共9页中国科学（信息科学）（英文版）

基　　金：supported by National Natural Science Foundation of China(Grant Nos.61872450,62172446,61802441).

摘　　要：The lower-bounded k-median problem plays a key role in many applications related to privacy protection, which requires that the amount of assigned client to each facility should not be less than the requirement. Unfortunately, the lower-bounded clustering problem remains elusive under the widely studied k-median objective. Within this paper, we convert this problem to the capacitated facility location problem and successfully give a(516+ε)-approximation for this problem.

关 键 词：approximation algorithm k-median lower-bounded k-median 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]