- Inapproximability of Minimum Diameter Clustering for Few Clusters
- Project Year:
2023
- REU Student (s):
Kyrylo Karlov | Charles University (Prague, Czech Republic)
| Ashwin Padaki | Columbia University in the City of New York NY
- Student 1 Institution:
Charles University (Prague, Czech Republic)
- Student 2 Institution:
Columbia University in the City of New York
- Project Mentor:
Karthik Srikanta
- Project Mentor Area:
Computer Science
- Project Abstract:
We consider the problem of approximate clustering with the diameter objective function. When the number of clusters is allowed to be unbounded, the inapproximability ratio is fairly well understood. However, this problem has not been well-studied when the number of clusters is constant. In this work, we show improved hardness bounds when there are a fixed number of clusters. Specifically, we show that the problem is hard to approximate within a factor of 1.5 in Hamming space, and within 1.304 in Euclidean space. Additionally, we prove several barrier results to known methods of proving hardness, and we provide a polynomial time algorithm for the problem when the number of dimensions is constant.
