Martín Costa

activity

20232026

k

-Center Clustering with Recourse

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

collaborators

Showing 2023Show all

4 papers · 1 filter

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

Arboricity-Dependent Algorithms for Edge Coloring

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

The problem of edge coloring has been extensively studied over the years. Recently, this problem has received significant attention in the dynamic setting, where we are given a dyn…

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.DS2023

Density-Sensitive Algorithms for $(Δ + 1)$ -Edge Coloring

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

Vizing's theorem asserts the existence of a $(Δ + 1)$ -edge coloring for any graph $G$ , where $Δ = Δ (G)$ denotes the maximum degree of $G$ . Several polynomial time $(Δ + 1)$ -edge colorin…

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

Arboricity-Dependent Algorithms for Edge Coloring

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

Density-Sensitive Algorithms for (Δ+1)-Edge Coloring

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

Density-Sensitive Algorithms for $(Δ + 1)$ -Edge Coloring