Red–Blue k -Center Clustering with Distance Constraints

Marzieh Eskandari (), Bhavika B. Khare, Nirman Kumar and Bahram Sadeghi Bigham
Additional contact information
Marzieh Eskandari: Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102, USA
Bhavika B. Khare: Department of Computer Science, University of Memphis, Memphis, TN 38152, USA
Nirman Kumar: Department of Computer Science, University of Memphis, Memphis, TN 38152, USA
Bahram Sadeghi Bigham: Department of Computer Science, Faculty of Mathematical Sciences, Alzahra University, Tehran 19938 93973, Iran

Mathematics, 2023, vol. 11, issue 3, 1-17

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.

Keywords: algorithms; facility location; computational geometry; clustering (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/3/748/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/3/748/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:3:p:748-:d:1054915

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().