51²è¹Ý

Dear All,

The department of computer science invites you to a seminar on "Approximation Algorithms for Clustering and Beyond"

Zoom Link: https://zoom.us/j/91640525117?pwd=3UPvvI8VPdxdtnISFm8DCuA2FR0oXx.1

Abstract: Clustering problems are central to many applications and have been studied through a variety of approximation paradigms, including combinatorial, geometric, probabilistic, and LP-based techniques. In this talk, we briefly survey these approaches, emphasizing both their applicability to different clustering objectives and our contributions within these respective frameworks. We then present recent results from our work on metric partitioning, where we develop a refined framework for hierarchical probabilistic partitions with strong worst-case guarantees, ensuring that each region interacts with only a bounded number of relevant cells. This structural property enables efficient dynamic programming and leads to improved algorithms for clustering objectives such as min-sum radii and min-sum diameters, aversion clustering and their variants, including new PTAS results in doubling and related metric spaces. Our framework further extends to network design problems, yielding improved bounds for problems such as the Traveling Salesman Problem and Steiner Tree.

About the Speaker: Sandip Banerjee is currently a senior post-doctoral fellow at SUPSI, IDSIA-USI, Switzerland. Before joining here, he was there at the University of Wroclaw, Poland as a research assistant professor and at the Hebrew University of Jerusalem, Israel as a postdoctoral fellow. He obtained his PhD from the Indian Statistical Institute, Kolkata (reg. IIEST), following an M.Sc from Chennai Mathematical Institute.  His research interests include approximation algorithms, computational geometry, clustering, metric embeddings, and parameterized complexity.

We look forward to your active participation.