Maximum-Weight Matching in Sliding Windows and Beyond

We study the maximum-weight matching problem in the sliding-window model. In this model, we are given an adversarially ordered stream of edges of an underlying edge-weighted graph G(V, E), and a parameter L specifying the window size, and we want to maintain an approximation of the maximum-weight matching of the current graph G(t); here G(t) is defined as the subgraph of G consisting of the edges that arrived during the time interval [max(t - L, 1), t], where t is the current time. The goal is to do this with Õ(n) space, where n is the number of vertices of G. We present a deterministic (3.5 + ε)-approximation algorithm for this problem, thus significantly improving the (6 + ε)-approximation algorithm due to Crouch and Stubbs [5]. We also present a generic machinery for approximating subadditive functions in the sliding-window model. A function f is called subadditive if for every disjoint substreams A, B of a stream S it holds that f(AB) ≤ f(A) + f(B), where AB denotes the concatenation of A and B. We show that given an α-approximation algorithm for a subadditive function f in the insertion-only model we can maintain a (2α + ε)-approximation of f in the sliding-window model. This improves upon recent result Krauthgamer and Reitblat [14], who obtained a (2α ² + ε)-approximation.