CAREER: Price of Clustering in Geometric Spaces: Inapproximability, Conditional Lower Bounds, and More

Clustering is the task of grouping objects so that those in the same group are more similar to each other than to those in other groups. It is widely used in unsupervised learning, data analysis, information retrieval, and community detection. This project contributes to the theory of clustering by aiming to understand the extent to which clustering can be efficiently approximated by leveraging tools and ideas from metric embedding, coding theory, extremal combinatorics, and analysis of Boolean functions.

Seeking the optimal inapproximability of clustering not only sheds light on problems important to the theoretical computer science community but also enriches other fields such as machine learning, data science, and computer vision, equipping future researchers in all these fields to tackle other geometric optimization problems effectively. The educational activities of this project include integrating findings into graduate and undergraduate courses, mentoring students, and broadening participation in theoretical computer science.

In technical terms, the primary goal of this project is to establish tight NP-hardness of approximation results for key clustering problems, such as minimizing k-means, k-median, and k-center objectives in L_p (i.e., L subscript p) metrics. A secondary goal is to study these objectives through the lenses of fine-grained complexity and the theory of stable instances.

The three main research directions are: (i) resolving the Johnson Coverage Hypothesis, (ii) determining tight hardness of approximation factors for popular clustering objectives in the Euclidean metric, and (iii) proving conditional lower bounds for the Euclidean k-means problem with fixed k.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.