The Parallel Seeding Algorithm for k-Means Problem with Penalties

Min Li (), Dachuan Xu (), Jun Yue () and Dongmei Zhang
Additional contact information
Min Li: School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, P. R. China
Dachuan Xu: Department of Operations Research and Scientific Computing, Beijing University of Technology, Beijing 100124, P. R. China
Jun Yue: School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, P. R. China
Dongmei Zhang: School of Computer Science and Technology, Shandong Jianzhu University, Jinan 250101, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2020, vol. 37, issue 04, 1-18

Abstract: As a classic NP-hard problem in machine learning and computational geometry, the k-means problem aims to partition a data point set into k clusters such that the sum of the squared distance from each point to its nearest center is minimized. The k-means problem with penalties, denoted by k-MPWP, generalizing the k-means problem, allows that some points can be paid some penalties instead of being clustered. In this paper, we study the seeding algorithm of k-MPWP and propose a parallel seeding algorithm for k-MPWP along with the corresponding theoretical analysis.

Keywords: Approximation algorithm; k-means; penalty; seeding algorithm; parallel (search for similar items in EconPapers)
Date: 2020
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595920400059
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:37:y:2020:i:04:n:s0217595920400059

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595920400059

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().