The Parallel Seeding Algorithm for k-Means Problem with Penalties
Min Li, Dachuan Xu, Jun Yue, Dongmei Zhang · Asia Pacific Journal of Operational Research · 2020
As a classic NP-hard problem in machine learning and computational geometry, the [Formula: see text]-means problem aims to partition a data point set into [Formula: see text] clusters such that the sum of the squared distance from each point to its nearest center is minimized. The [Formula: see text]-means problem with penalties, denoted by [Formula: see text]-MPWP, generalizing the [Formula: see text]-means problem, allows that some points can be paid some penalties instead of being clustered. In this paper, we study the seeding algorithm of [Formula: see text]-MPWP and propose a parallel seeding algorithm for [Formula: see text]-MPWP along with the corresponding theoretical analysis.