On the Local Structure of Stable Clustering Instances

Vincent Cohen-Addad, Chris Schwiegelshohn

We study the classic $k$-median and $k$-means clustering objectives in the beyond-worst-case scenario. We consider three well-studied notions of structured data that aim at charact…