1 citations · 4 across the 12 of their papers we have counts for
14 papers · 1 filter
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…
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 transl…
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…
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-of-…
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…
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 i…
Fully Dynamic -Clustering with Fast Update Time and Small Recourse
Sayan Bhattacharya, Martín Costa, Naveen Garg +2
In the dynamic metric -median problem, we wish to maintain a set of centers in an input metric space that gets updated via point insertions/deletion…
Faster -Edge Coloring: Breaking the Time Barrier
Sayan Bhattacharya, Din Carmon, Martín Costa +2
Vizing's theorem states that any -vertex -edge graph of maximum degree can be {\em edge colored} using at most different colors [Diskret.~Analiz, '64]. Vizing's or…
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 -edge coloring in a dynamic graph with nodes and maximum degree at most . The state-of-the-art update time is $O_ε(\text…
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…
Fully Dynamic -Clustering in Update Time
Sayan Bhattacharya, Martín Costa, Silvio Lattanzi +1
We present a -approximate fully dynamic algorithm for the -median and -means problems on metric spaces with amortized update time and worst-case query tim…
Density-Sensitive Algorithms for -Edge Coloring
Sayan Bhattacharya, Martín Costa, Nadav Panski +1
Vizing's theorem asserts the existence of a -edge coloring for any graph , where denotes the maximum degree of . Several polynomial time -edge colorin…