Dr Joachim Spoerhase’s paper will be presented at the 64th IEEE Symposium on Foundations of Computer Science (FOCS) 2023 in California in November:
The paper proposes an algorithm for clustering objects by similarity, which is a fundamental task in data analysis, unsupervised learning, and numerous further areas of application such as location planning and logistics. When parameterised by the number of clusters, the algorithm efficiently computes a near-optimal solution. Such algorithms were previously limited to basic clustering problems such as k-means, k-median, and k-center, and tailored to specific types of similarity measures. In contrast, the new algorithm is applicable to almost all previously studied objective functions in center-based clustering and to a diverse range of similarity measures in a simple and entirely uniform way.
Dr Joachim Spoerhase, Lecturer in Algorithms in the Department of Computer Science, said: “The IEEE Symposium on Foundations of Computer Science (FOCS) is one of the two flagship conferences in theoretical computer science together with its sister conference, the ACM Symposium on Theory of Computing (STOC).
“These two conferences are widely recognised as the most prestigious and selective venues for publishing research in theoretical computer science worldwide. This recognition from the theory community acts to further cement our Foundations of Computation research group’s position as an important global player.”
It is the latest success for the growing research group, whose researchers had two papers accepted at the STOC 2023 conference earlier in the year.