Back to Search
Start Over
An approximation algorithm for the uniform capacitated k-means problem.
- Source :
- Journal of Combinatorial Optimization; Oct2022, Vol. 44 Issue 3, p1812-1823, 12p
- Publication Year :
- 2022
-
Abstract
- In this paper, we consider the uniform capacitated k-means problem (UC-k-means), an extension of the classical k-means problem (k-means) in machine learning. In the UC-k-means, we are given a set D of n points in d-dimensional space and an integer k. Every point in the d-dimensional space has an uniform capacity which is an upper bound on the number of points in D that can be connected to this point. Every two-point pair in the space has an associated connecting cost, which is equal to the square of the distance between these two points. We want to find at most k points in the space as centers and connect every point in D to some center without violating the capacity constraint, such that the total connecting costs is minimized. Based on the technique of local search, we present a bi-criteria approximation algorithm, which has a constant approximation guarantee and violates the cardinality constraint within a constant factor, for the UC-k-means. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 13826905
- Volume :
- 44
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- Journal of Combinatorial Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 159382637
- Full Text :
- https://doi.org/10.1007/s10878-020-00550-y