By Sandip Banerjee, Dalle Molle Institute for Artificial Intelligence, Lugano

Abstract 

Clustering is one of the central optimization problems in unsupervised learning, with many natural objective functions that are NP-hard to optimize exactly. This has motivated the development of approximation algorithms that provide provable guarantees while exploiting the underlying geometric and combinatorial structure of the input. In this talk, I will begin with a brief overview of several classical clustering objectives and the algorithmic techniques used to design approximation algorithms for them. I will then present the outline of our work published at FOCS 2024 (https://ieeexplore.ieee.org/abstract/document/10756173), which introduces a refined construction of hierarchical probabilistic partitions with significantly stronger structural properties than previously known. These properties lead to improved exact and approximation algorithms for a broad class of clustering problems, including the first PTASs for several objectives in doubling metrics. Finally, I will discuss the results of our AAAI 2025 work (https://dl.acm.org/doi/10.1609/aaai.v39i15.33699) and ongoing research that generalizes this framework to richer clustering objectives and constrained settings. Beyond clustering, I will highlight how the same framework yields improved algorithms for fundamental network design problems, including the Traveling Salesman Problem and the Steiner Tree Problem, etc.