8 papers
Incremental Submodular Maximization: Better Than Greedy
Marcin Bienkowski, Joakim Blikstad, JarosÅaw Byrka +3
We consider submodular maximization under increasing cardinality constraint and ask for a good incremental solution, i.e., an ordering of the ground set such that each prefix of th…
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…
Deterministic -Median Clustering in Near-Optimal Time
MartÃn Costa, Ermiya Farokhnejad
The metric -median problem is a textbook clustering problem. As input, we are given a metric space of size and an integer , and our task is to find a subset $S \subse…
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…