2026-07-25T13:21:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15506 2024-03-06T10:55:28Z ddc:004 open_access

Maximum-Weight Matching in Sliding Windows and Beyond Biabani, Leyla de Berg, Mark Monemizadeh, Morteza maximum-weight matching sliding-window model approximation algorithm and subadditve functions 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 [Michael S. Crouch and Daniel M. Stubbs, 2014]. We also present a generic machinery for approximating subadditve 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 [Robert Krauthgamer and David Reitblat, 2019], who obtained a (2α²+ε)-approximation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Leyla Biabani and Mark de Berg and Morteza Monemizadeh 2021 Is Part Of LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2021.73 urn:nbn:de:0030-drops-155061 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.73 eng https://creativecommons.org/licenses/by/4.0/legalcode