An exact algorithm for stable instances of the $ k $-means problem with penalties in fixed-dimensional Euclidean space

Fan Yuan; Dachuan Xu; Donglei Du; Min Li

doi:10.3934/jimo.2021122

Article Contents

2022, Volume 18, Issue 5: 3487-3498. Doi: 10.3934/jimo.2021122

This issue Previous Article Robust optimal asset-liability management with penalization on ambiguity Next Article Optimal replenishment, pricing and preservation technology investment policies for non-instantaneous deteriorating items under two-level trade credit policy

An exact algorithm for stable instances of the $ k $-means problem with penalties in fixed-dimensional Euclidean space

1.
Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing 100124, China
2.
Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, China
3.
Faculty of Management, University of New Brunswick, Fredericton, NB Canada E3B 5A3, Canada
4.
School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, China

^* Corresponding author: Dachuan Xu
^* Corresponding author: Dachuan Xu

Received: September 30, 2020

Revised: April 30, 2021

Early access: July 2021

Published: November 2022

Abstract Full Text(HTML) Related Papers Cited by

Abstract

We study stable instances of the $ k $-means problem with penalties in fixed-dimensional Euclidean space. An instance of the problem is called $ \alpha $-stable if this instance exists a sole optimal solution and the solution keeps unchanged when distances and penalty costs are scaled by a factor of no more than $ \alpha $. Stable instances of clustering problem have been used to explain why certain heuristic algorithms with poor theoretical guarantees perform quite well in practical. For any fixed $ \epsilon > 0 $, we show that when using a common multi-swap local-search algorithm, a $ (1+\epsilon) $-stable instance of the $ k $-means problem with penalties in fixed-dimensional Euclidean space can be solved accurately in polynomial time.

Keywords:

Mathematics Subject Classification: Primary: 90C27; Secondary: 68W25.

Citation:

FullText(HTML)

Related Papers

Cited by

References

[1]	S. Ahmadian, A. Norouzi-Fard, O. Svensson and J. Ward, Better guarantees for $k$-means and Euclidean $k$-median by primal-dual algorithms, 58th Annual IEEE Symposium on Foundations of Computer Science-FOCS, (2017), 61-72. doi: 10.1137/18M1171321.
[2]	D. Aloise, A. Deshpande, P. Hansen and P. Popat, NP-hardness of Euclidean sum-of-squares clustering, Machine Learning, 75 (2009), 245-248. doi: 10.1007/s10994-009-5103-0.
[3]	H. Angelidakis, K. Makarychev and Y. Makarychev, Algorithms for stable and perturbation-resilient problems, STOC'17-Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, (2017), 438-451. doi: 10.1145/3055399.3055487.
[4]	V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala and V. Pandit, Local search heuristics for $k$-median and facility location problems, SIAM J. Comput., 33 (2004), 544-562. doi: 10.1137/S0097539702416402.
[5]	P. Awasthi, A. Blum and O. Sheffet, Stability yields a PTAS for $k$-median and $k$-means clustering, 2010 IEEE 51st Annual Symposium on Foundations of Computer Science-FOCS, (2010), 309-318. doi: 10.1109/FOCS. 2010.36.
[6]	P. Awasthi, A. Blum and O. Sheffet, Center-based clustering under perturbation stability, Inform. Process. Lett., 112 (2012), 49-54. doi: 10.1016/j.ipl.2011.10.006.
[7]	M. F. Balcan and Y. Liang, Clustering under perturbation resilience, SIAM J. Comput., 45 (2016), 102-155. doi: 10.1137/140981575.
[8]	Y. Bilu and N. Linial, Are stable instances easy?, Combin. Probab. Comput., 21 (2012), 643-660. doi: 10.1017/S0963548312000193.
[9]	M. Charikar and S. Guha, Improved combinatorial algorithms for the facility location and $k$-median problems, 40th Annual Symposium on Foundations of Computer Science (New York, 1999), (1999), 378-388. doi: 10.1109/SFFCS. 1999.814609.
[10]	V. Cohen-Addad, P. N. Klein and C. Mathieu, Local search yields approximation schemes for $k$-means and $k$-median in Euclidean and minor-free metrics, SIAM J. Comput., 48 (2019), 644-667. doi: 10.1137/17M112717X.
[11]	P. Drineas, A. Frieze, R. Kannan, S. Vempala and V. Vinay, Clustering large graphs via the singular value decomposition, Machine Learning, 56 (2004), 9-33. doi: 10.1023/B:MACH.0000033113.59016.96.
[12]	D. Du, X. Wang and D. Xu, An approximation algorithm for the $k$-level capacitated facility location problem, J. Comb. Optim., 20 (2010), 361-368. doi: 10.1007/s10878-009-9213-1.
[13]	Q. Feng, Z. Zhang, F. Shi and J. Wang, An improved approximation algorithm for the $k$-means problem with penalties, Proceedings of FAW, (2019), 170-181. doi: 10.1007/978-3-030-18126-0_15.
[14]	Z. Friggstad, K. Khodamoradi and M. R. Salavatipour, Exact algorithms and lower bounds for stable instances of Euclidean $k$-means, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, (2019), 2958-2972. doi: 10.1137/1.9781611975482.183.
[15]	Z. Friggstad, M. Rezapour and M. R. Salavatipour, Local search yields a PTAS for $k$-means in doubling metrics, 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), (2016), 365-374. doi: 10.1109/focs. 2016.47.
[16]	S. Ji, D. Xu, L. Guo, M. Li and D. Zhang, The seeding algorithm for spherical $k$-means clustering with penalties, Journal of Combinatorial Optimization, (2020, Accepted). doi: 10.1007/s10878-020-00569-1.
[17]	T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman and A. Y. Wu, A local search approximation algorithm for $k$-means clustering, Comput. Geom., 28 (2004), 89-112. doi: 10.1016/j.comgeo.2004.03.003.
[18]	M. Li, The bi-criteria seeding algorithms for two variants of $k$-means problem, J. Comb. Optim., (2020, Accepted). doi: 10.1007/s10878-020-00537-9.
[19]	M. Li, D. Xu, J. Yue, D. Zhang and P. Zhang, The seeding algorithm for $k$-means problem with penalties, J. Comb. Optim., 39 (2020), 15-32. doi: 10.1007/s10878-019-00450-w.
[20]	A.-Y. Liang and D. Lin, Crossover iterated local search for SDCARP, J. Oper. Res. Soc. China, 2 (2014), 351-367. doi: 10.1007/s40305-014-0056-9.
[21]	M. Mahajan, P. Nimbhorkar and K. Varadarajan, The planar $k$-means problem is NP-hard, Proceedings of WALCOM, 5431 (2009), 274-285. doi: 10.1007/978-3-642-00202-1_24.
[22]	J. Matoušek, On approximate geometric $k$-clustering, Discrete Comput. Geom., 24 (2000), 61-84. doi: 10.1007/s004540010019.
[23]	G. C. Tseng, Penalized and weighted $k$-means for clustering with scattered objects and prior information in high-throughput biological data, Bioinformatics, (2007), 2247-2255. doi: 10.1093/bioinformatics/btm320.
[24]	H. Yang, F. Li, D. Yu, Y. Zou and J. Yu, Reliable data storage in heterogeneous wireless sensor networks by jointly optimizing routing and storage node deployment, Tsinghua Science and Technology, 26 (2021), 230-238. doi: 10.26599/TST.2019.9010061.
[25]	D. Ye, L. Mei and Y. Zhang, Strategy-proof mechanism for obnoxious facility location on a line, Proceedings of COCOON, 9198 (2015), 45-56. doi: 10.1007/978-3-319-21398-9_4.
[26]	D. Zhang, C. Hao, C. Wu, D. Xu and Z. Zhang, Local search approximation algorithms for the $k$-means problem with penalties, J. Comb. Optim., 37 (2019), 439-453. doi: 10.1007/s10878-018-0278-6.
[27]	Y. Zhang, F. Y. L. Chin and H. Zhu, A 1-local asymptotic 13/9-competitive algorithm for multicoloring hexagonal graphs, Algorithmica, 54 (2009), 557-567. doi: 10.1007/s00453-008-9203-1.