Naveen Garg is the Janaki and KA Iyer Chair Professor in the Computer Science and Engineering Department at IIT Delhi.

Homepage: https://www.cse.iitd.ac.in/~naveen/index.html

AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

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/deletions, to minimize the objective $\sum_{x \in V}
\min_{y \in S} d(x, y)$. The quality of a dynamic algorithm is measured in terms of its approximation ratio, ``recourse'' (the number of changes in $S$ per update) and ``update time'' (the time it takes to handle an update). The
ultimate goal in this line of research is to obtain a dynamic $O(1)$ approximation algorithm with $\tilde{O}(1)$ recourse and $\tilde{O}(k)$ update time.

We come close to resolving this goal by adapting a randomized local search to the dynamic setting. For every $\epsilon > 0$, we give a dynamic $k$-median algorithm with $O(1/\epsilon)$ approximation ratio, $\tilde{O}(k^{\epsilon})$ recourse and $\tilde{O}(k^{1+\epsilon})$ update time. This framework also generalizes to dynamic $k$-clustering with $\ell^p$-norm objectives. As a corollary, we obtain similar bounds for the dynamic $k$-means problem, and a new trade-off between approximation ratio, recourse and update time for the dynamic $k$-center problem.

Joint work with Sayan Bhattacharya, Martin Costa (U. Warwick), Silvio Lattanzi, Nikos Parotsidis (Google Zurich)

Nidhi Rathi

+49 681 9325 1134

--email hidden

Zoom

897 027 2575

passcode not visible

logged in users only