March 4 - 6, 2024
Workshop: Old Questions and New Directions in Theory of Clustering
at EnCORE, UCSD
In this workshop, our primary goal is to reinvigorate collaboration between the approximation and computational geometry communities. We aim to delve deeper into understanding various popular clustering objectives, such as k-means, k-median, k-center, k-minsum, capacitated clustering, balanced clustering, correlation clustering, and k-diameter under the approximation lens.
In this workshop, our primary goal is to reinvigorate collaboration between the approximation and computational geometry communities. We aim to delve deeper into understanding various popular clustering objectives, such as k-means, k-median, k-center, k-minsum, capacitated clustering, balanced clustering, correlation clustering, and k-diameter under the approximation lens.
The workshop will emphasize on making progress on these objectives in the Euclidean metric, to determine if the rich geometric structure can be exploited to develop efficient algorithms for the above clustering objectives with approximation guarantees better than those in arbitrary metric spaces. Despite the puzzling scarcity of algorithms leveraging the structure of high-dimensional L_p-metrics to surpass general metric settings, exploring this research direction holds the potential to yield improved algorithms with practical impact. Moreover, it offers an opportunity to gain a deeper understanding of the structure inherent in these fundamental metrics.
The workshop will emphasize on making progress on these objectives in the Euclidean metric, to determine if the rich geometric structure can be exploited to develop efficient algorithms for the above clustering objectives with approximation guarantees better than those in arbitrary metric spaces. Despite the puzzling scarcity of algorithms leveraging the structure of high-dimensional L_p-metrics to surpass general metric settings, exploring this research direction holds the potential to yield improved algorithms with practical impact. Moreover, it offers an opportunity to gain a deeper understanding of the structure inherent in these fundamental metrics.
Some concrete questions that will be brainstormed include finding a better than 2 factor approximation algorithm for Euclidean k-center problem and leveraging recent synergies in the study of correlation clustering in general metric to get better guarantees for Euclidean correlation clustering.
Some concrete questions that will be brainstormed include finding a better than 2 factor approximation algorithm for Euclidean k-center problem and leveraging recent synergies in the study of correlation clustering in general metric to get better guarantees for Euclidean correlation clustering.
Let us know if you'll be attending!
Let us know if you'll be attending!
Organizers:
Karthik C. S. (Rutgers University)
Euiwoong Lee (University of Michigan)
Pasin Manurangsi (Google)
Chris Schwiegelshohn (Aarhus University)