4.5 Article

The provably good parallel seeding algorithms for the k-means problem with penalties

Journal

Publisher

WILEY
DOI: 10.1111/itor.12808

Keywords

approximation algorithm; k-means; k-means problem with penalties; parallel seeding algorithm

Funding

  1. Higher Educational Science and Technology Program of Shandong Province [J17KA171]
  2. Natural Science Foundation of Shandong Province [ZR2019MA032]
  3. National Natural Science Foundation of China [11871081]

Ask authors/readers for more resources

This paper focuses on the parallel seeding algorithm for the k-MPWP problem and provides sufficient analysis on the expected solution quality. The numerical experiment demonstrates the effectiveness of the parallel algorithm for k-means with penalties.
As a classic NP-hard problem in machine learning and computational geometry, the k-means problem aims to partition the given points into k sets to minimize the within-cluster sum of squares. The k-means problem with penalties (k-MPWP), as a generalizing problem of the k-means problem, allows a point that can be either clustered or penalized with some positive cost. In this paper, we mainly apply the parallel seeding algorithm to the k-MPWP, and show sufficient analysis to bound the expected solution quality in the case where both the number of iterations and the number of points sampled in each iteration can be given arbitrarily. The approximate guarantee can be obtained as O(f(M)lnk), where f(M) is a polynomial function involving the maximal ratio M between the penalties. On one hand, this result can be viewed as a further improvement on the parallel algorithm for k-MPWP given by Li et al., where the number of iterations depends on other factors. On the other hand, our result also generalizes the one solving the k-means problem presented by Bachem et al., because k-MPWP is a variant of the k-means problem. Moreover, we present a numerical experiment to show the effectiveness of the parallel algorithm for k-means with penalties.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.5
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available