Indexed by:
Abstract:
In the classical k-means problem, we are given a data set D subset of R-l and an integer k. The object is to select a set S subset of R-l of size at most k such that each point in D is connected to the closet cluster in S with minimum total squared distances. However, in some real-life applications, it is more desirable and beneficial to pay a small penalty for not connecting some outliers in D that are too far away from most points. As a result, we are motivated to study the k-means problem with penalties, for which we propose a (6.357+epsilon)-approximation algorithm via the primal-dual technique, improving the previous best approximation ratio of 19.849 + is an element of in [7] also by using the primal-dual technique.
Keyword:
Reprint Author's Address:
Email:
Source :
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2020
ISSN: 0302-9743
Year: 2020
Volume: 12337
Page: 377-389
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: