86b8ad667206fb9a52ae575fbf1cd6be-Paper-Conference.pdf

In this paper, we study the fundamental problems of maintaining the diameter and a k-center clustering of a dynamic point set P Rd, where points may be inserted or deleted over time and the ambient dimension dis not constant and may be high. Our focus is on designing algorithms that remain effective even in the presence of an adaptive adversary--an adversary that, at any time t, knows the entire history of the algorithm's outputs as well as all the random bits used by the algorithm up to that point. We present a fully dynamic algorithm that maintains a 2-approximate diameter with a worst-case update time of poly(d,logn), where n is the length of the stream. Our result is achieved by identifying a robust representative of the dataset that requires infrequent updates, combined with a careful deamortization. To the best of our knowledge, this is the first efficient fully-dynamic algorithm for diameter in high dimensions that simultaneously achieves a 2-approximation guarantee and robustness against an adaptive adversary. We also give an improved dynamic (4+ϵ)-approximation algorithm for the k-center problem, also resilient to an adaptive adversary.