Local search yields a PTAS for fixed-dimensional k-means problem with penalties  

作　　者：Fan Yuan Da-Chuan Xu Dong-Lei Du Dong-Mei Zhang 

机构地区：[1]Beijing Institute for Scientific and Engineering Computing,Beijing University of Technology,Beijing 100124,China [2]Faculty of Management,University of New Brunswick,Fredericton,NB E3B 9Y2,Canada [3]School of Computer Science and Technology,Shandong Jianzhu University,Jinan 250101,Shandong,China

出　　处：《Journal of the Operations Research Society of China》2024年第2期351-362,共12页中国运筹学会会刊（英文）

基　　金：the National Natural Science Foundation of China(No.12131003);Beijing Natural Science Foundation Project(No.Z200002);the Natural Sciences and Engineering Research Council of Canada(No.06446);the National Natural Science Foundation of China(Nos.11771386 and 11728104);the National Natural Science Foundation of China(No.11871081)。

摘　　要：We study a problem called the k-means problem with penalties(k-MPWP),which is a natural generalization of the typical k-means problem.In this problem,we have a set D of client points in R^(d),a set F of possible centers in R^(d),and a penalty cost Pj>O for each point j∈D.We are also given an integer k which is the size of the center point set.We want to find a center point set S■F with size k,choose a penalized subset of clients P■D,and assign every client in D\P to its open center.Our goal is to minimize the sum of the squared distances between every point in D\P to its assigned centre point and the sum of the penalty costs for all clients in P.By using the multi-swap local search technique and under the fixed-dimensional Euclidean space setting,we present a polynomial-time approximation scheme(PTAS)for the k-MPWP.

关 键 词：Approximation algorithm K-MEANS Local search PENALTY 

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