Martín Costa

most citedFully Dynamic

k

-Clustering in

O ~ (k)

Update Time

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

collaborators

3 papers

cs.DS2024★ 1 cited

Fully Dynamic $k$ -Clustering with Fast Update Time and Small Recourse

Sayan Bhattacharya, Martín Costa, Naveen Garg +2

In the dynamic metric $k$ -median problem, we wish to maintain a set of $k$ centers $S \subseteq V$ in an input metric space $(V, d)$ that gets updated via point insertions/deletion…

cs.DS2023

Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time

Sayan Bhattacharya, Martín Costa, Nadav Panski +1

We consider the problem of maintaining a $(1 + ε) Δ$ -edge coloring in a dynamic graph $G$ with $n$ nodes and maximum degree at most $Δ$ . The state-of-the-art update time is $O_ε(\text…

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…

Fully Dynamic k-Clustering with Fast Update Time and Small Recourse

Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time

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

Fully Dynamic $k$ -Clustering with Fast Update Time and Small Recourse

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