Anupam Gupta, New York University (NYU)

Abstract

A recent line of work asks: given a clustering optimization problem (like k-means or k-medians), how does the cost of the best explainable clustering compare to that of the best clustering? We consider the model where a clustering is called explainable if it can be defined by a tree of axis-parallel cuts. Building on a recent sequence of works, we pin down the optimal price of explainability for k-median clustering, and also improve on existing results for k-means clustering. In this talk, I will discuss some of these results (both ours and prior results), the techniques underlying them, and point out some of the open questions in the area. 

This talk is based on this paper (https://arxiv.org/abs/2304.09743) with Madhusudhan Pittu (CMU), Ola Svensson (EPFL), and Rachel Yuan (CMU).

See: https://theory.cs.rutgers.edu/theory_seminar