• Previous Article
    Error estimates for spectral approximation of flow optimal control problem with $ L^2 $-norm control constraint
  • JIMO Home
  • This Issue
  • Next Article
    Research on optimal pricing decisions of the service supply chain oriented to strategic consumers
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 and 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.

[2]

D. AloiseA. DeshpandeP. 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. AryaN. GargR. KhandekarA. MeyersonK. 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. AwasthiA. 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-AddadP. 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. DrineasA. FriezeR. KannanS. 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. DuX. 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. KanungoD. M. MountN. S. NetanyahuC. D. PiatkoR. 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. LiD. XuJ. YueD. 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. MahajanP. 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. YangF. LiD. YuY. 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. YeL. 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. ZhangC. HaoC. WuD. 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. ZhangF. 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.

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.

[2]

D. AloiseA. DeshpandeP. 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. AryaN. GargR. KhandekarA. MeyersonK. 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. AwasthiA. 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-AddadP. 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. DrineasA. FriezeR. KannanS. 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. DuX. 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. KanungoD. M. MountN. S. NetanyahuC. D. PiatkoR. 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. LiD. XuJ. YueD. 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. MahajanP. 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. YangF. LiD. YuY. 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. YeL. 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. ZhangC. HaoC. WuD. 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. ZhangF. 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.

[1]

Min Li, Yishui Wang, Dachuan Xu, Dongmei Zhang. The approximation algorithm based on seeding method for functional $ k $-means problem. Journal of Industrial and Management Optimization, 2022, 18 (1) : 411-426. 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 and Management Optimization, 2022, 18 (4) : 2277-2287. 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 and 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 and 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 and 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 and 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]

Yasemin Cengellenmis, Abdullah Dertli, Steven T. Dougherty, Adrian Korban, Serap Şahinkaya, Deniz Ustun. Reversible $ G $-codes over the ring $ {\mathcal{F}}_{j,k} $ with applications to DNA codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021056

[11]

Bassam Fayad, Maria Saprykina. Realizing arbitrary $d$-dimensional dynamics by renormalization of $C^d$-perturbations of identity. Discrete and Continuous Dynamical Systems, 2022, 42 (2) : 597-604. doi: 10.3934/dcds.2021129

[12]

Liyuan Tian, Yong Wang. Solving tensor complementarity problems with $ Z $-tensors via a weighted fixed point method. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022093

[13]

Silvia Frassu. Nonlinear Dirichlet problem for the nonlocal anisotropic operator $ L_K $. Communications on Pure and Applied Analysis, 2019, 18 (4) : 1847-1867. doi: 10.3934/cpaa.2019086

[14]

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

[15]

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 and Continuous Dynamical Systems - S, 2021, 14 (7) : 2119-2135. doi: 10.3934/dcdss.2021063

[16]

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

[17]

Habibul Islam, Om Prakash, Ram Krishna Verma. New quantum codes from constacyclic codes over the ring $ R_{k,m} $. Advances in Mathematics of Communications, 2022, 16 (1) : 17-35. doi: 10.3934/amc.2020097

[18]

Harbir Antil, Mahamadi Warma. Optimal control of the coefficient for the regional fractional $p$-Laplace equation: Approximation and convergence. Mathematical Control and Related Fields, 2019, 9 (1) : 1-38. doi: 10.3934/mcrf.2019001

[19]

Purshottam Narain Agrawal, Jitendra Kumar Singh. Better approximation by a Durrmeyer variant of $ \alpha- $Baskakov operators. Mathematical Foundations of Computing, 2022  doi: 10.3934/mfc.2021040

[20]

Jinrong Wang, Michal Fečkan, Yi Guan. Constant vorticity atmospheric Ekman flows in the $ f- $plane approximation. Discrete and Continuous Dynamical Systems - B, 2022  doi: 10.3934/dcdsb.2022012

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (372)
  • HTML views (406)
  • Cited by (0)

Other articles
by authors

[Back to Top]