Back to Search
Start Over
Red–Blue k -Center Clustering with Distance Constraints.
- Source :
-
Mathematics (2227-7390) . Feb2023, Vol. 11 Issue 3, p748. 17p. - Publication Year :
- 2023
-
Abstract
- We consider a variant of the k-center clustering problem in I R d , where the centers can be divided into two subsets—one, the red centers of size p, and the other, the blue centers of size q, such that p + q = k , and each red center and each blue center must be a distance of at least some given α ≥ 0 apart. The aim is to minimize the covering radius. We provide a bi-criteria approximation algorithm for the problem and a polynomial time algorithm for the constrained problem where all centers must lie on a given line ℓ. Additionally, we present a polynomial time algorithm for the case where only the orientation of the line is fixed in the plane ( d = 2 ), although the algorithm works even in I R d by constraining the line to lie in a plane and with a fixed orientation. [ABSTRACT FROM AUTHOR]
- Subjects :
- *APPROXIMATION algorithms
*POLYNOMIAL time algorithms
*COMPUTATIONAL geometry
Subjects
Details
- Language :
- English
- ISSN :
- 22277390
- Volume :
- 11
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Mathematics (2227-7390)
- Publication Type :
- Academic Journal
- Accession number :
- 161857512
- Full Text :
- https://doi.org/10.3390/math11030748