4 papers
A General Reduction from Near-Additive Emulators to Near-Exact Hopsets
Julian Aeri, Sebastian Forster, Mara Grilnberger
Graph emulators and hopsets are two fundamental concepts for distance approximation. When the multiplicative stretch is for arbitrarily small , these structures are kn…
Adaptive Fully Dynamic -Center Clustering with (Near-)Optimal Worst-Case Guarantees
Mara Grilnberger, Antonis Skarlatos
Given a sequence of adversarial point insertions and point deletions, is it possible to simultaneously optimize the approximation ratio, update time, and recourse for a -cluster…
A Weighted-to-Unweighted Reduction for Matroid Intersection
Aditi Dudeja, Mara Grilnberger
Given two matroids and over the same ground set, the matroid intersection problem is to find the maximum cardinality common independent set. In the…
Dynamic Matroids: Base Packing and Covering
Tijn de Vos, Mara Grilnberger
In this paper, we consider dynamic matroids, where elements can be inserted to or deleted from the ground set over time. The independent sets change to reflect the current ground s…