Indexed by:
Abstract:
In this paper, we consider the Bregman k-means problem (BKM) which is a variant of the classical k-means problem. For an n-point set S and k <= n with respect to mu-similar Bregman divergence, the BKM problem aims first to find a center subset C subset of S with vertical bar C vertical bar= k and then separate S into k clusters according to C, such that the sum of mu-similarBregman divergence from each point in S to its nearest center is minimized. We propose a mu-similar BregMeans++ algorithm by employing the local search scheme, and prove that the algorithm deserves a constant approximation guarantee. Moreover, we extend our algorithm to solve a variant of BKM called noisy mu-similar Bregman k-means++ (noisy mu-BKM++) which is BKM in the noisy scenario. For the same instance and purpose as BKM, we consider the case of sampling a point with an imprecise probability by a factor between 1- epsilon(1) and 1+ epsilon(2) for epsilon(1) is an element of epsilon[0, 1) and epsilon(2) >= 0, and obtain an approximation ratio of O(log(2) k) in expectation.
Keyword:
Reprint Author's Address:
Source :
JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN: 1382-6905
Year: 2021
Issue: 4
Volume: 44
Page: 2533-2550
1 . 0 0 0
JCR@2022
ESI Discipline: MATHEMATICS;
ESI HC Threshold:31
JCR Journal Grade:3
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 10
Affiliated Colleges: