Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds

Coresets are arguably the most popular compression paradigm for center-based clustering objectives such as $k$-means. Given a point set $P$, a coreset $Ω$ is a small, weighted summary that preserves the cost of all candidate solutions $S$ up to a $(1\pm \varepsilon)$ factor. For $k$-means in $d$-dim...

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής

Κύριοι συγγραφείς:	Bansal, Nikhil, Cohen-Addad, Vincent, Prabhu, Milind, Saulpic, David, Schwiegelshohn, Chris
Μορφή:	Άρθρο
Έκδοση:	2024
Θέματα:	Data Structures and Algorithms
Διαθέσιμο Online:	https://arxiv.org/abs/2405.01339 http://arxiv.org/abs/2405.01339
Ετικέτες:	Προσθήκη ετικέτας Δεν υπάρχουν, Καταχωρήστε ετικέτα πρώτοι!