Journal of the Operations Research Society of China >

2024 , Vol. 12 >Issue 2: 351 - 362

DOI: https://doi.org/10.1007/s40305-022-00394-9

Local search yields a PTAS for fixed-dimensional k-means problem with penalties

Expand
  • 1 Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, China;
    2 Faculty of Management, University of New Brunswick, Fredericton, NB E3B 9Y2, Canada;
    3 School of Computer Science and Technology, Shandong Jianzhu University, Jinan 250101, Shandong, China

Received date: 2020-09-20

  Revised date: 2021-11-03

  Online published: 2024-06-12

Supported by

The first two authors are supported by the National Natural Science Foundation of China (No. 12131003) and Beijing Natural Science Foundation Project (No. Z200002). The third author is supported by the Natural Sciences and Engineering Research Council of Canada (No.06446), and the National Natural Science Foundation of China (Nos. 11771386 and 11728104). The fourth author is supported by the National Natural Science Foundation of China (No. 11871081).

Fold

Abstract

We study a problem called the k-means problem with penalties (k-MPWP), which is a natural generalization of the typical k-means problem. In this problem, we have a set D of client points in ℝd, a set F of possible centers in ℝd, and a penalty cost pj > 0 for each point j ∈ D. We are also given an integer k which is the size of the center point set. We want to find a center point set S ⊆ F with size k, choose a penalized subset of clients P ⊆ D, and assign every client in D\P to its open center. Our goal is to minimize the sum of the squared distances between every point in D\P to its assigned centre point and the sum of the penalty costs for all clients in P. By using the multi-swap local search technique and under the fixed-dimensional Euclidean space setting, we present a polynomial-time approximation scheme (PTAS) for the k-MPWP.

Key words： Approximation algorithm; k-means; Local search; Penalty

Cite this article

Fan Yuan, Da-Chuan Xu, Dong-Lei Du, Dong-Mei Zhang . Local search yields a PTAS for fixed-dimensional k-means problem with penalties[J]. Journal of the Operations Research Society of China, 2024 , 12(2) : 351 -362 . DOI: 10.1007/s40305-022-00394-9

References

[1] Charikar, M., Khuller, S., Mount, D. M., Narasimhan, G.:Algorithms for facility location problems with outliers. In:Proceedings of Symposium on Discrete Algorithms, pp 642-651(2001)
[2] Hajiaghayi, M., Khandekar, R., Kortsarz, G.:Local search algorithms for the redblue median problem. Algorithmica 63(4), 795-814(2012)
[3] Wu, C., Du, D., Xu, D.:An approximation algorithm for the k-median problem with uniform penalties via pseudo-solution. Theor. Comput. Sci. 749, 80-92(2018)
[4] Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.:Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6), 795-824(2003)
[5] Li, Y., Du, D., Xiu, N., Xu, D.:Improved approximation algorithms for the facility location problems with linear/submodular penalties. Algorithmica 73(2), 460-482(2015)
[6] Xu, G., Xu, J.:An improved approximation algorithm for uncapacitated facility location problem with penalties. J. Comb. Optim. 17(4), 424-436(2009)
[7] Feng, Q., Zhang, Z., Shi, F., Wang, J.:An improved approximation algorithm for the k-means problem with penalties. In:Proceedings of FAW, pp. 170-181(2019) https://doi.org/10.1007/978-3-030-18126-0_15
[8] Zhang, D., Hao, C., Wu, C., Xu, D., Zhang, Z.:Local search approximation algorithms for the k-means problem with penalties. J. Comb. Optim. 37(2), 439-453(2019)
[9] Aloise, D., Deshpande, A., Hansen, P., Popat, P.:NP-hardness of Euclidean sum-of-squares clustering. Mach. Learn. 75(2), 245-248(2009)
[10] Dasgupta, S.:The hardness of-means clustering (Technical Report CS2008-0916). Department of Computer Science and Engineering. University of California, San Diego (2008)
[11] Mahajan, M., Nimbhorkar, P., Varadarajan, K.:The planar k-means problem is NP-hard. In:Proceedings of WALCOM, pp 274-285(2009) https://doi.org/10.1016/j.tcs.2010.05.034
[12] Lloyd, S.:Least squares quantization in PCM. IEEE Trans. Inf. Theory 28(2), 129-137(1982)
[13] Matoušek, J.:On approximate geometric k-clustering. Discret. Comput. Geom. 24(1), 61-84(2000)
[14] Jain, K., Vazirani, V.V.:Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48(2), 274-296(2001)
[15] Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D., Silverman, R., Wu, A.Y.:A local search approximation algorithm for k-means clustering. Comput. Geom. 28(2-3), 89-112(2004)
[16] Ahmadian, S., Norouzi-Fard, A., Svensson, O., Ward, J.:Better guarantees for k-means and Euclidean k-median by primal-dual algorithms. In:Proceedings of Annual Symposium on Foundations of Computer Science, pp 61-72(2017)
[17] Charikar, M., Guha, S.:Improved combinatorial algorithms for the facility location and k-median problems. In:Proceedings of Annual Symposium on Foundations of Computer Science, pp 378-388(1999)
[18] Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.:Local search heuristics for k-median and facility location problems. SIAM J. Comput. 33(3), 544-562(2004)
[19] Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K.:An improved approximation for k-median, and positive correlation in budgeted optimization. ACM Trans. Algorithms 13(2), 737-756(2017)
[20] Friggstad, Z., Rezapour, M., Salavatipour, M. R.:Local search yields a PTAS for k-means in doubling metrics. In:Proceedings of Annual Symposium on Foundations of Computer Science, pp 365-374(2016)
[21] Cohen-Addad, V., Klein, P. N., Mathieu, C.:Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics. In:Proceedings of Annual Symposium on Foundations of Computer Science, pp 353-364(2016)
[22] Cohen-Addad, V.:A fast approximation scheme for low-dimensional k-means. In:Proceedings of SODA, pp 430-440(2018)
[23] Arora, S., Raghavan, P., Rao, S.:Approximation schemes for Euclidean k-medians and related problems. In:Proceedings of STOC, pp 106-113(1998) https://doi.org/10.1145/276698.276718
[24] Arora, S.:Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753-782(1998)
Options
Outlines

/

〈 〉

Copyright © Operations Research Society of China, The Periodicals Agency of Shanghai University , and Springer-Verlag Berlin Heidelberg 2016