Online Facility Location against a t-Bounded Adversary
Harry Lang · Society for Industrial and Applied Mathematics eBooks · 2018
In the streaming model, the order of the stream can significantly affect the difficulty of a problem. A t-semirandom stream was introduced as an interpolation between random-order (t = 1) and adversarial-order (t = n) streams where an adversary intercepts a random-order stream and can delay up to t elements at a time. IITK Sublinear Open Problem #15 asks to find algorithms whose performance degrades smoothly as t increases. We show that the celebrated online facility location algorithm achieves an expected competitive ratio of . We present a matching lower bound that any randomized algorithm has an expected competitive ratio of . We use this result to construct an O(1)-approximate streaming algorithm for k-median clustering that stores O(k log t) points and has O(k log t) worst-case update time. Our technique generalizes to any dissimilarity measure that satisfies a weak triangle inequality, including k-means, M-estimators, and ℓp norms. The special case t = 1 yields an optimal O(k) space algorithm for random-order streams as well as an optimal O(nk) time algorithm in the RAM model, closing a long line of research on this problem.