2017/11/26 by Lang, Harry
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1711.09384
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 O((log t)/(log log t)). We present a matching lower bound that any randomized algorithm has an expected competitive ratio of Ω((log t)/(log log t)). 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.