Approximation Algorithms for Spherical k-Means Problem with Penalties Using Local Search Techniques

Xiaoyun Tian (), Ling Gai, Yicheng Xu () and Dongmei Zhang ()
Additional contact information
Xiaoyun Tian: Department of Operations, Research and Information Engineering, Beijing University of Technology, Beijing 100124, P. R. China
Ling Gai: Glorious Sun School of Business and Management, Donghua University, Shanghai 200051, P. R. China
Yicheng Xu: Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Shenzhen, 518055, 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), 2023, vol. 40, issue 01, 1-16

Abstract: In this paper, we consider the spherical k-means problem with penalties, a robust model of spherical clusterings that requires identifying outliers during clustering to improve the quality of the solution. Each outlier will incur a specified penalty cost. In this problem, one should detect the outliers and propose a k-clustering for the given data set so as to minimize the sum of the clustering and penalty costs. As our main contribution, we present a (16 + 83)-approximation via single-swap local search and an (8 + 27 + 𠜀)-approximation via multi-swap local search.

Keywords: Spherical k-means; outlier; adapted clustering; local search; approximation algorithm (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595922400140
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:40:y:2023:i:01:n:s0217595922400140

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595922400140

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 ().