Seminar Details
The Price of Explainability for Clustering
- Start Date: April 3, 2024
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Anupam Gupta - New York University (NYU)
- Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
- Event Additional Info: <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar">https://theory.cs.rutgers.edu/theory_seminar</a></p>
- Presentation Type: Stand Alone Presentation
- 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).