An approximation algorithm for k-median with priorities

作     者：Zhen ZHANG Qilong FENG Jinhui XU Jianxin WANG Zhen ZHANG;Qilong FENG;Jinhui XU;Jianxin WANG

作者机构：School of Computer Science and Engineering Central South University Department of Computer Science and Engineering State University of New York at Buffalo 

出 版 物：《Science China(Information Sciences)》 (中国科学:信息科学(英文版))

年 卷 期：2021年第64卷第5期

页      面：45-46页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported by National Natural Science Foundation of China (Grant Nos. 61872450, 61672536, 61828205, 61802441, 71631008) Hunan Provincial Key Lab on Bioinformatics, and Hunan Provincial Science and Technology Program (Grant No. 2018WK4001) 

主　　题：Clustering k median approximation algorithm LP relaxtion primal-dual 

摘      要：Dear editor,Clustering is a fundamental problem in computer *** problem is to partition a given set of clients into several clusters such that clients in the same cluster are more similar to each other. In many clustering applications, the clients are different in the levels of services they require. Motivated by such applications, Ravi and Sinha [1] introduced the problem of clustering with priorities, wherein each client is associated with a priority and can only be assigned to a facility opened at the same or higher priorities.