Abstract
We study the maximumweight matching problem in the slidingwindow model. In this model, we are given an adversarially ordered stream of edges of an underlying edgeweighted graph G(V,E), and a parameter L specifying the window size, and we want to maintain an approximation of the maximumweight 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(tL,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 [Michael S. Crouch and Daniel M. Stubbs, 2014].
We also present a generic machinery for approximating subadditve functions in the slidingwindow 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 insertiononly model we can maintain a (2α+ε)approximation of f in the slidingwindow model. This improves upon recent result Krauthgamer and Reitblat [Robert Krauthgamer and David Reitblat, 2019], who obtained a (2α²+ε)approximation.
BibTeX  Entry
@InProceedings{biabani_et_al:LIPIcs.ISAAC.2021.73,
author = {Biabani, Leyla and de Berg, Mark and Monemizadeh, Morteza},
title = {{MaximumWeight Matching in Sliding Windows and Beyond}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {73:173:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772143},
ISSN = {18688969},
year = {2021},
volume = {212},
editor = {Ahn, HeeKap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15506},
URN = {urn:nbn:de:0030drops155061},
doi = {10.4230/LIPIcs.ISAAC.2021.73},
annote = {Keywords: maximumweight matching, slidingwindow model, approximation algorithm, and subadditve functions}
}
Keywords: 

maximumweight matching, slidingwindow model, approximation algorithm, and subadditve functions 
Collection: 

32nd International Symposium on Algorithms and Computation (ISAAC 2021) 
Issue Date: 

2021 
Date of publication: 

30.11.2021 