Algorithms for covering and clustering in the sliding window model
Marina Knittle (UCSD)
Monday, November 4th 2024, 2-3pm
Abstract:
We present new results for the $\gamma$-covering and $k$-center problems in the sliding window model: a model of online computation in which one data point arrives at each time step and where the goal is to always maintain an approximately-optimal solution for the most recent $W$ points. The $\gamma$-cover problem consists of maintaining a dynamic set of centers $C_t$, with minimum cardinality, such that each point in the sliding window of the most recent $W$ points is at distance at most $\gamma$ of $C_t$. We present a $6$-approximation algorithm and we show that a $(2-\epsilon)$-approximation cannot be achieved. For the $k$-center problem we give a lower bound that establishes the optimality of a recently-proposed algorithm that has significant space complexity. We show, however, that if we are permitted to compare to the best solution for the most recent $2W$ points (a relaxed sliding window) then there is a simpler and more efficient scheme. We also present a sliding window version of the popular cover tree data structure.