6 papers
Fully Dynamic Euclidean k-Means
Sayan Bhattacharya, MartÃn Costa, Ermiya Farokhnejad +3
We consider the Euclidean -means clustering problem in a dynamic setting, where we have to explicitly maintain a solution (a set of centers) subje…
Vizing's Theorem in Deterministic Almost-Linear Time
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya +3
Vizing's theorem states that any -vertex -edge graph of maximum degree can be edge colored using at most different colors. Vizing's original proof is easily tran…
Vizing's Theorem in Near-Linear Time
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya +3
Vizing's theorem states that any -vertex -edge graph of maximum degree can be edge colored using at most different colors [Vizing, 1964]. Vizing's original proof…
Almost Optimal Fully Dynamic -Center Clustering with Recourse
Sayan Bhattacharya, MartÃn Costa, Ermiya Farokhnejad +2
In this paper, we consider the \emph{metric -center} problem in the fully dynamic setting, where we are given a metric space evolving via a sequence of point insertions…
Fully Dynamic -Median with Near-Optimal Update Time and Recourse
Sayan Bhattacharya, MartÃn Costa, Ermiya Farokhnejad
In metric -clustering, we are given as input a set of points in a general metric space, and we have to pick centers and cluster the input points around these chosen cent…
Even Faster -Edge Coloring via Shorter Multi-Step Vizing Chains
Sayan Bhattacharya, MartÃn Costa, Shay Solomon +1
Vizing's Theorem from 1964 states that any -vertex -edge graph with maximum degree can be {\em edge colored} using at most colors. For over 40 years, the state-o…