Abstract
We consider capacitated k-means clustering whose object is to minimize the within-cluster sum of squared Euclidean distances. The task is to partition a set of n observations into k disjoint clusters satisfying the capacity constraints, both upper and lower bound capacities are considered. One of the reasons making these clustering problems hard to deal with is the continuous choices of the centroid. In this paper we propose a discretization algorithm that in polynomial time outputs an approximate centroid set with at most \(\epsilon \) fractional loss of the original object. This result implies an FPT(k,d) PTAS for uniform capacitated k-means and makes more techniques, for example local search, possible to apply to it.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
An, H.C., Bhaskara, A., Chekuri, C., Gupta, S., Madan, V., Svensson, O.: Centrality of trees for capacitated \(k\)-center. Math. Program. 154(1–2), 29–53 (2015)
Byrka J., Fleszar K., Rybicki B., Spoerhase J.: Bi-factor approximation algorithms for hard capacitated k-median problems. In: Proceedings of the 26th Annual ACMSIAM Symposium on Discrete Algorithms, pp. 722–736. SIAM, San Diego, USA (2015)
Chen X., Cai D.: Large scale spectral clustering with landmark-based representation. In: Proceedings of the 25th AAAI Conference on Artificial Intelligence, pp. 313–318. AAAI, San Francisco, USA (2011)
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 the 57th IEEE Annual Symposium on Foundations of Computer Science, pp. 353–364. IEEE, New Brunswick, USA (2016)
Friggstad Z., Rezapour M., Salavatipour M.R.: Local search yields a PTAS for \(k\)-means in doubling metrics. In: Proceedings of the 57th IEEE Annual Symposium on Foundations of Computer Science, pp. 365–374. IEEE, New Brunswick, USA (2016)
Geetha S., Poonthalir G., Vanathi P.: Improved \(k\)-means algorithm for capacitated clustering problem. In: Proceedings of the 28th IEEE Conference on Computer Communications, pp. 52–59. IEEE, Rio de Janeiro, Brazil (2009)
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)
Li, S.: On uniform capacitated \(k\)-median beyond the natural LP Relaxation. ACM Trans. Algorithms 13(2), 1–22 (2017)
Matoušek, J.: On approximate geometric \(k\)-clustering. Discret. Comput. Geom. 24(1), 61–84 (2000)
Shen X., Liu W., Tsang I., Shen F., Sun Q.: Compressed \(k\)-means for large-scale clustering. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence, pp. 2527–2533. AAAI, San Francisco, USA (2017)
Acknowledgement
The first author is supported by China Postdoctoral Science Foundation funded project (No. 2018M643233). The second author is supported by Natural Science Foundation of China(Nos. 11531014, 11871081). The third author is supported by Higher Educational Science and Technology Program of Shandong Province (No. J15LN23). The fourth author is supported by Natural Science Foundation of China (Nos. 61433012, U1435215).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Xu, Y., Xu, D., Zhang, D., Zhang, Y. (2020). A Discretization Algorithm for k-Means with Capacity Constraints. In: Le Thi, H., Le, H., Pham Dinh, T. (eds) Optimization of Complex Systems: Theory, Models, Algorithms and Applications. WCGO 2019. Advances in Intelligent Systems and Computing, vol 991. Springer, Cham. https://doi.org/10.1007/978-3-030-21803-4_71
Download citation
DOI: https://doi.org/10.1007/978-3-030-21803-4_71
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-21802-7
Online ISBN: 978-3-030-21803-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)