Improved local search algorithms for Bregman k-means and its variants

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 $${\mathcal {S}}$$ S and $$k \le n$$ k ≤ n with respect to $$\mu $$ μ -similar Bregman divergence, the BKM problem aims first to find a center subset $$C \subseteq {\mathcal {S}}$$ C ⊆ S with $$ \mid C \mid = k$$ ∣ C ∣ = k and then separate $${\mathcal {S}}$$ S into k clusters according to C, such that the sum of $$\mu $$ μ -similar Bregman divergence from each point in $${\mathcal {S}}$$ 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-\varepsilon _1$$ 1 - ε 1 and $$1+ \varepsilon _2$$ 1 + ε 2 for $$\varepsilon _1 \in [0,1)$$ ε 1 ∈ [ 0 , 1 ) and $$\varepsilon _2 \ge 0$$ ε 2 ≥ 0 , and obtain an approximation ratio of $$O(\log ^2 k)$$ O ( log 2 k ) in expectation.