Yasamin Nazari

Emilio Cruciani, Sebastian Forster, Gramoz Goranci et al.

In this paper we give the first efficient algorithms for the $k$-center problem on dynamic graphs undergoing edge updates. In this problem, the goal is to partition the input into $k$ sets by choosing $k$ centers such that the maximum distance from any data point to its closest center is minimized. It is known that it is NP-hard to get a better than $2$ approximation for this problem. While in many applications the input may naturally be modeled as a graph, all prior works on $k$-center problem in dynamic settings are on point sets in arbitrary metric spaces. In this paper, we give a deterministic decremental $(2+ε)$-approximation algorithm and a randomized incremental $(4+ε)$-approximation algorithm, both with amortized update time $kn^{o(1)}$ for weighted graphs. Moreover, we show a reduction that leads to a fully dynamic $(2+ε)$-approximation algorithm for the $k$-center problem, with worst-case update time that is within a factor $k$ of the state-of-the-art fully dynamic $(1+ε)$-approximation single-source shortest paths algorithm in graphs. Matching this bound is a natural goalpost because the approximate distances of each vertex to its center can be used to maintain a $(2+ε)$-approximation of the graph diameter and the fastest known algorithms for such a diameter approximation also rely on maintaining approximate single-source distances.

Ben Bals, Joakim Blikstad, Greg Bodwin et al.

For many popular graph metric sparsifiers, such as spanners, emulators, and preservers, simple and elegant greedy algorithms are known that achieve state-of-the-art or existentially optimal tradeoffs between size and quality. The goal of this paper is to develop and analyze comparable greedy algorithms for nearby objects in graph metric augmentation. We show the following: - A simple greedy algorithm for shortcut sets achieves the state-of-the-art size/hopbound tradeoff recently proved by Kogan and Parter (2022), up to $O(\log n)$ factors in the size. Moreover, with an additional preprocessing step, the greedy algorithm subpolynomially improves on the previous size bounds in some range of parameters. - The same greedy algorithm was already known to be existentially optimal for the size/hopbound tradeoff for hopsets, by an analysis of Berman, Raskhodnikova, and Ruan (2010) introduced for transitive-closure spanners. We provide a completely different analysis showing that the algorithm is also existentially optimal (up to $O(\log n)$ factors) for the matching hopset problem, in which one has a budget of roughly $O(m)$ additional edges (for an $m$-edge input graph).

Sebastian Forster, Yasamin Nazari, Rajath Rao K. N. et al.

In this paper, we study the $(k,z)$-clustering and $k$-center problems on graphs, where $(k,z)$-clustering generalizes the $k$-median ($z=1$) and $k$-means ($z=2$) problems. We obtain the following main results. Our first contribution is the first deterministic algorithm for $k$-center on graphs that achieves a $(2+\varepsilon)$-approximation in $\tilde{O}(m)$ time. This affirmatively resolves an open problem raised by Abboud, Cohen-Addad, Lee, and Manurangsi [SOSA 2023]. Our techniques also extend to the $k$-center with outliers problem, where up to $t$ points may be discarded. Our second contribution is a randomized algorithm for $(k,z)$-clustering on graphs that achieves an $O(1)$-approximation in $\tilde{O}(m)$ time, which in particular covers $k$-median ($z=1$) and $k$-means ($z=2$). Prior to this work, an $\tilde{O}(m)$-time randomized algorithm was known for $k$-median by Thorup [SIAM J. Comput. 2005], and a recent work of Jiang, Jin, Lou, and Lu [2026] achieves $m^{1+o(1)}$ time for general $z$ via local search. Finally, we design a deterministic algorithm for $(k,z)$-clustering on graphs that achieves an $O(\mathrm{poly}(c))$-approximation in $\tilde{O}(m^{1+1/c})$ time, for a positive parameter $c$. To obtain this result, we use techniques from the Thorup-Zwick distance oracle [JACM 2005]; this technical connection may be of independent interest, considering the wide application of distance oracles in various computational settings. Most of our algorithms are incremental, in the sense that for any given parameter $k$, they return a sequence of centers such that every prefix of length $\ell \leq k$ yields a constant-factor approximate solution to the $\ell$-clustering problem.