Parameterized Approximation Algorithms and Lower Bounds for K-Center Clustering and Variants
Published In
Algorithmica
Document Type
Citation
Publication Date
5-13-2024
Abstract
k-center is one of the most popular clustering models. While it admits a simple 2-approximation in polynomial time in general metrics, the Euclidean version is NP-hard to approximate within a factor of 1.82, even in the plane, if one insists the dependence on k in the running time be polynomial. Without this restriction, a classic algorithm by Agarwal and Procopiuc yields...
Rights
© 2024 Springer Nature
Locate the Document
DOI
10.1007/s00453-024-01236-1
Persistent Identifier
https://archives.pdx.edu/ds/psu/42023
Citation Details
Bandyapadhyay, S., Friggstad, Z., & Mousavi, R. (2024). Parameterized Approximation Algorithms and Lower Bounds for k-Center Clustering and Variants. Algorithmica.
COinS