We consider the Maximum-weight Matching (MWM) problem in the streaming sliding window model of computation. In this model, the input consists of a sequence of weighted edges on a given vertex set $V$ of size $n$. The objective is to maintain an approximation of a maximum-weight matching in the graph spanned by the $L$ most recent edges, for some integer $L$, using as little space as possible. Prior to our work, the state-of-the-art results were a $(3.5+\varepsilon)$-approximation algorithm for MWM by Biabani et al. [ISAAC'21] and a $(3+\varepsilon)$-approximation for (unweighted) Maximum Matching (MM) by Crouch et al. [ESA'13]. Both algorithms use space $\tilde{O}(n)$. We give the following results: 1. We give a $(2+\varepsilon)$-approximation algorithm for MWM with space $\tilde{O}(\sqrt{nL})$. Under the reasonable assumption that the graphs spanned by the edges in each sliding window are simple, our algorithm uses space $\tilde{O}(n \sqrt{n})$. 2. In the $\tilde{O}(n)$ space regime, we give a $(3+\varepsilon)$-approximation algorithm for MWM, thereby closing the gap between the best-known approximation ratio for MWM and MM. Similar to Biabani et al.'s MWM algorithm, both our algorithms execute multiple instances of the $(2+\varepsilon)$-approximation $\tilde{O}(n)$-space streaming algorithm for MWM by Paz and Schwartzman [SODA'17] on different portions of the stream. Our improvements are obtained by selecting these substreams differently. Furthermore, our $(2+\varepsilon)$-approximation algorithm runs the Paz-Schwartzman algorithm in reverse direction over some parts of the stream, and in forward direction over other parts, which allows for an improved approximation guarantee at the cost of increased space requirements.
翻译:我们认为在滚动滑动窗口计算模型中存在最大重量匹配(MWM)问题。 在这个模型中, 输入由给定的顶端设定的加权边距序列 $V 美元大小。 目标是在图形中保持最大重量匹配的近似值, 以最近一点的边距为美元, 使用尽可能小的空间 。 在我们工作之前, 最新的结果是 Biabani 和 Al. [ SAAC' 21] 给MWM 设定的 $( 3. Varepsl) 平流比值比值比值比值比值的比值比值比值比值的比值比值比值 。 两种算都使用了空间 $tilde{O} 最大比值比值的比值比值比值比值比值比值比值的比值比值( =2\ valepsl) 和比值比值比值比值比值比值的M( =) 我们的比值比值比值比值比值比值比值比值比值比值比值比值比值增加。