Almost-Smooth Histograms and Sliding-Window Graph Algorithms
share
We study algorithms for the sliding-window model, an important variant of the data-stream model, in which the goal is to compute some function of a fixed-length suffix of the stream. We explore the smooth histogram framework of Braverman and Ostrovsky (FOCS 2007) for reducing the sliding-window model to the insertion-only streaming model, and extend it to the family of subadditive functions. Specifically, we show that if a subadditive function can be approximated in the ordinary (insertion-only) streaming model, then it could be approximated also in the sliding-window model with approximation ratio larger by factor 2+ϵ and space complexity larger by factor O(ϵ^-1 w), where w is the window size. We then consider graph streams and show that many graph problems are subadditive, including maximum matching and minimum vertex-cover, thereby deriving sliding-window algorithms for them almost for free (using known insertion-only algorithms). One concrete example is a polylog(n)-space algorithm for estimating maximum-matching size in bounded-arboricity graphs with n vertices, whose approximation ratio differs by a factor of 2 from the insertion-only algorithm of McGregor and Vorotnikova (SODA 2018). We also use the same framework to improve the analysis of a known sliding-window algorithm for approximating minimum vertex-cover in general graphs. We improve the approximation ratio 8+ϵ of van Handel (MSc Thesis 2016) to 4+ϵ using the same space complexity Õ_ϵ(n).
READ FULL TEXT