Silvio Lattanzi

activity

20232026

k

-Clustering with Fast Update Time and Small Recourse

1 citations · 4 across the 11 of their papers we have counts for

collaborators

Showing 2023Show all

3 papers · 1 filter

cs.DS2023

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams

Ainesh Bakshi, Vincent Cohen-Addad, Samuel B. Hopkins +2

Metric embeddings are a widely used method in algorithm design, where generally a ``complex'' metric is embedded into a simpler, lower-dimensional one. Historically, the theoretica…

cs.DS2023★ 1 cited

Fully Dynamic $k$ -Clustering in $O ~ (k)$ Update Time

Sayan Bhattacharya, Martín Costa, Silvio Lattanzi +1

We present a $O (1)$ -approximate fully dynamic algorithm for the $k$ -median and $k$ -means problems on metric spaces with amortized update time $O ~ (k)$ and worst-case query tim…

cs.CG2023

Multi-Swap $k$ -Means++

Lorenzo Beretta, Vincent Cohen-Addad, Silvio Lattanzi +1

The $k$ -means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is often the practitioners' choice algorithm for optimizing the popular $k$ -means clustering objective and is know…

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams

Fully Dynamic k-Clustering in O~(k) Update Time

Multi-Swap k-Means++

Fully Dynamic $k$ -Clustering in $O ~ (k)$ Update Time

Multi-Swap $k$ -Means++