Abstract
We consider the Maximumweight 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 maximumweight 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 stateoftheart results were a (3.5+ε)approximation algorithm for MWM by Biabani et al. [ISAAC'21] and a (3+ε)approximation for (unweighted) Maximum Matching (MM) by Crouch et al. [ESA'13]. Both algorithms use space Õ(n).
We give the following results:
1) We give a (2+ε)approximation algorithm for MWM with space Õ(√{nL}). Under the reasonable assumption that the graphs spanned by the edges in each sliding window are simple, our algorithm uses space Õ(n √n).
2) In the Õ(n) space regime, we give a (3+ε)approximation algorithm for MWM, thereby closing the gap between the bestknown approximation ratio for MWM and MM.
Similar to Biabani et al.’s MWM algorithm, both our algorithms execute multiple instances of the (2+ε)approximation Õ(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+ε)approximation algorithm runs the PazSchwartzman 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.
BibTeX  Entry
@InProceedings{alexandru_et_al:LIPIcs.STACS.2023.6,
author = {Alexandru, CezarMihail and Dvo\v{r}\'{a}k, Pavel and Konrad, Christian and Naidu, Kheeran K.},
title = {{Improved Weighted Matching in the Sliding Window Model}},
booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
pages = {6:16:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772662},
ISSN = {18688969},
year = {2023},
volume = {254},
editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17658},
URN = {urn:nbn:de:0030drops176585},
doi = {10.4230/LIPIcs.STACS.2023.6},
annote = {Keywords: Sliding window algorithms, Streaming algorithms, Maximumweight matching}
}
Keywords: 

Sliding window algorithms, Streaming algorithms, Maximumweight matching 
Collection: 

40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) 
Issue Date: 

2023 
Date of publication: 

03.03.2023 