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

doi:10.1007/s40305-022-00394-9

Journal of the Operations Research Society of China ›› 2024, Vol. 12 ›› Issue (2): 351-362.doi: 10.1007/s40305-022-00394-9

Previous Articles Next Articles

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

Fan Yuan¹, Da-Chuan Xu¹, Dong-Lei Du², Dong-Mei Zhang³

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:2020-09-20 Revised:2021-11-03 Online:2024-06-30 Published:2024-06-12
Contact: Dong-Mei Zhang, Fan Yuan, Da-Chuan Xu, Dong-Lei Du E-mail:zhangdongmei@sdjzu.edu.cn;yuanfan@emails.bjut.edu.cn;xudc@bjut.edu.cn;ddu@unb.ca
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).

Abstract

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

CLC Number:

90C27

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.

TrendMD

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)

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Wen-Zhao Liu, Min Li. An Approximation Algorithm Based on Seeding Algorithm for Fuzzy k-Means Problem with Penalties [J]. Journal of the Operations Research Society of China, 2024, 12(2): 387-409.
[2]	Bin Liu, Hui Su, Shu-Fang Gong, Qi-Zhi Fang. Adaptive Algorithms on Maximizing Monotone Nonsubmodular Functions [J]. Journal of the Operations Research Society of China, 2024, 12(2): 428-445.
[3]	Hong-Ye Zheng, Suo-Gang Gao, Wen Liu, Bo Hou. An Approximation Algorithm for the Parallel-Machine Customer Order Scheduling with Delivery Time and Submodular Rejection Penalties [J]. Journal of the Operations Research Society of China, 2024, 12(2): 495-504.
[4]	Amina Sabir, Peng-Fei Huang, Qing-Zhi Yang. The Low-Rank Approximation of Fourth-Order Partial-Symmetric and Conjugate Partial-Symmetric Tensor [J]. Journal of the Operations Research Society of China, 2023, 11(4): 735-758.
[5]	Zhong-Zheng Tang, Zhuo Diao. Approximation Algorithms on k-Correlation Clustering [J]. Journal of the Operations Research Society of China, 2023, 11(4): 911-924.
[6]	Wei Yu, Rui-Yong Dai, Zhao-Hui Liu. Approximation Algorithms for Multi-vehicle Stacker Crane Problems [J]. Journal of the Operations Research Society of China, 2023, 11(1): 109-132.
[7]	Jin-Shuang Guo, Wen Liu, Bo Hou. An Approximation Algorithm for P-prize-collecting Set Cover Problem [J]. Journal of the Operations Research Society of China, 2023, 11(1): 207-218.
[8]	Zhong-Zheng Tang, Zhuo Diao. Approximation Algorithms on k-Cycle Transversal and k-Clique Transversal [J]. Journal of the Operations Research Society of China, 2021, 9(4): 883-892.
[9]	June Liu, Tao Zhang, Yu-Xin Fan, Bing Han, Yue Zheng. An Objective Penalty Method for Optimistic Bilevel Programming Problems [J]. Journal of the Operations Research Society of China, 2020, 8(1): 177-187.
[10]	Ru-Bing Chen, Ling-Fa Lu, Jin-Jiang Yuan, Li-Qi Zhang. Improved Approximation Algorithm for Scheduling on a Serial Batch Machine with Split-Allowed Delivery [J]. Journal of the Operations Research Society of China, 2020, 8(1): 133-143.
[11]	Yao Xu, Yong Chen, Peng Zhang, Randy Goebel. Approximation Algorithms for Vertex Happiness [J]. Journal of the Operations Research Society of China, 2019, 7(3): 429-448.
[12]	Tao-Ran Fu, Jin-Yan Fan. Successive Partial-Symmetric Rank-One Algorithms for Almost Unitarily Decomposable Conjugate Partial-Symmetric Tensors [J]. Journal of the Operations Research Society of China, 2019, 7(1): 147-167.
[13]	Lu Han · Da-Chuan Xu · Dong-Lei Du·Chen-Chen Wu. A Primal-Dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem [J]. Journal of the Operations Research Society of China, 2017, 5(2): 219-.
[14]	Anurag Jayswal · Jonaki Banerjee. An Exact l1 Penalty Approach for Interval-ValuedProgramming Problem [J]. Journal of the Operations Research Society of China, 2016, 4(4): 461-.
[15]	Fang Liu,Ke Liu,Xin-Li Xie. Monitoring and Limiting Deceptive Counterfeiting:a Two-Stage Model [J]. Journal of the Operations Research Society of China, 2016, 4(3): 265-.