# American Institute of Mathematical Sciences

• Previous Article
Supply chain coordination considering e-tailer's promotion effort and logistics provider's service effort
• JIMO Home
• This Issue
• Next Article
A three echelon supply chain model with stochastic demand dependent on price, quality and energy reduction
doi: 10.3934/jimo.2021122
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

## 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

Received  October 2020 Revised  May 2021 Early access July 2021

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.

Citation: Fan Yuan, Dachuan Xu, Donglei Du, Min Li. An exact algorithm for stable instances of the $k$-means problem with penalties in fixed-dimensional Euclidean space. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2021122
##### 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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [7] M. F. Balcan and Y. Liang, Clustering under perturbation resilience, SIAM J. Comput., 45 (2016), 102-155.  doi: 10.1137/140981575.  Google Scholar [8] Y. Bilu and N. Linial, Are stable instances easy?, Combin. Probab. Comput., 21 (2012), 643-660.  doi: 10.1017/S0963548312000193.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [22] J. Matoušek, On approximate geometric $k$-clustering, Discrete Comput. Geom., 24 (2000), 61-84.  doi: 10.1007/s004540010019.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar

show all references

##### 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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [7] M. F. Balcan and Y. Liang, Clustering under perturbation resilience, SIAM J. Comput., 45 (2016), 102-155.  doi: 10.1137/140981575.  Google Scholar [8] Y. Bilu and N. Linial, Are stable instances easy?, Combin. Probab. Comput., 21 (2012), 643-660.  doi: 10.1017/S0963548312000193.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [22] J. Matoušek, On approximate geometric $k$-clustering, Discrete Comput. Geom., 24 (2000), 61-84.  doi: 10.1007/s004540010019.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar
 [1] Min Li, Yishui Wang, Dachuan Xu, Dongmei Zhang. The approximation algorithm based on seeding method for functional $k$-means problem†. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020160 [2] Chenchen Wu, Wei Lv, Yujie Wang, Dachuan Xu. Approximation algorithm for spherical $k$-means problem with penalty. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021067 [3] Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $k$-facility location problem with linear penalties. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056 [4] Xavier Gràcia, Xavier Rivas, Narciso Román-Roy. Erratum: Constraint algorithm for singular field theories in the $k$-cosymplectic framework. Journal of Geometric Mechanics, 2021, 13 (2) : 273-275. doi: 10.3934/jgm.2021007 [5] Ekta Mittal, Sunil Joshi. Note on a $k$-generalised fractional derivative. Discrete & Continuous Dynamical Systems - S, 2020, 13 (3) : 797-804. doi: 10.3934/dcdss.2020045 [6] Haisheng Tan, Liuyan Liu, Hongyu Liang. Total $\{k\}$-domination in special graphs. Mathematical Foundations of Computing, 2018, 1 (3) : 255-263. doi: 10.3934/mfc.2018011 [7] Yong Xia, Ruey-Lin Sheu, Shu-Cherng Fang, Wenxun Xing. Double well potential function and its optimization in the $N$ -dimensional real space-part Ⅱ. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1307-1328. doi: 10.3934/jimo.2016074 [8] Shu-Cherng Fang, David Y. Gao, Gang-Xuan Lin, Ruey-Lin Sheu, Wenxun Xing. Double well potential function and its optimization in the $N$ -dimensional real space-part Ⅰ. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1291-1305. doi: 10.3934/jimo.2016073 [9] Jianqin Zhou, Wanquan Liu, Xifeng Wang, Guanglu Zhou. On the $k$-error linear complexity for $p^n$-periodic binary sequences via hypercube theory. Mathematical Foundations of Computing, 2019, 2 (4) : 279-297. doi: 10.3934/mfc.2019018 [10] Bassam Fayad, Maria Saprykina. Realizing arbitrary $d$-dimensional dynamics by renormalization of $C^d$-perturbations of identity. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021129 [11] Silvia Frassu. Nonlinear Dirichlet problem for the nonlocal anisotropic operator $L_K$. Communications on Pure & Applied Analysis, 2019, 18 (4) : 1847-1867. doi: 10.3934/cpaa.2019086 [12] Adam Kanigowski, Federico Rodriguez Hertz, Kurt Vinhage. On the non-equivalence of the Bernoulli and $K$ properties in dimension four. Journal of Modern Dynamics, 2018, 13: 221-250. doi: 10.3934/jmd.2018019 [13] Habibul Islam, Om Prakash, Ram Krishna Verma. New quantum codes from constacyclic codes over the ring $R_{k,m}$. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020097 [14] Yu-Ming Chu, Saima Rashid, Fahd Jarad, Muhammad Aslam Noor, Humaira Kalsoom. More new results on integral inequalities for generalized $\mathcal{K}$-fractional conformable Integral operators. Discrete & Continuous Dynamical Systems - S, 2021, 14 (7) : 2119-2135. doi: 10.3934/dcdss.2021063 [15] Huaning Liu, Yixin Ren. On the pseudorandom properties of $k$-ary Sidel'nikov sequences. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021038 [16] Harbir Antil, Mahamadi Warma. Optimal control of the coefficient for the regional fractional $p$-Laplace equation: Approximation and convergence. Mathematical Control & Related Fields, 2019, 9 (1) : 1-38. doi: 10.3934/mcrf.2019001 [17] Burak Ordin, Adil Bagirov, Ehsan Mohebi. An incremental nonsmooth optimization algorithm for clustering using $L_1$ and $L_\infty$ norms. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2757-2779. doi: 10.3934/jimo.2019079 [18] Nicholas J. Kass, Mohammad A. Rammaha. Local and global existence of solutions to a strongly damped wave equation of the $p$-Laplacian type. Communications on Pure & Applied Analysis, 2018, 17 (4) : 1449-1478. doi: 10.3934/cpaa.2018070 [19] Gyu Eun Lee. Local wellposedness for the critical nonlinear Schrödinger equation on $\mathbb{T}^3$. Discrete & Continuous Dynamical Systems, 2019, 39 (5) : 2763-2783. doi: 10.3934/dcds.2019116 [20] Xiaopeng Zhao. Space-time decay estimates of solutions to liquid crystal system in $\mathbb{R}^3$. Communications on Pure & Applied Analysis, 2019, 18 (1) : 1-13. doi: 10.3934/cpaa.2019001

2020 Impact Factor: 1.801

## Tools

Article outline

Figures and Tables