Biabani, Leyla ;
de Berg, Mark ;
Monemizadeh, Morteza
MaximumWeight Matching in Sliding Windows and Beyond
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}
}
30.11.2021
Keywords: 

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

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

Issue date: 

2021 
Date of publication: 

30.11.2021 