TY - CONF

T1 - Maximum-Weight Matching in Sliding Windows and Beyond.

AU - Biabani, Leyla

AU - Berg, Mark de

AU - Monemizadeh, Morteza

N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2021/12/1

Y1 - 2021/12/1

N2 - 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 [5]. 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 [14], who obtained a (2α
2 + ε)-approximation.

AB - 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 [5]. 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 [14], who obtained a (2α
2 + ε)-approximation.

KW - Approximation algorithm

KW - Maximum-weight matching

KW - Sliding-window model

KW - Subadditve functions

UR - http://www.scopus.com/inward/record.url?scp=85122441380&partnerID=8YFLogxK

U2 - 10.4230/LIPICS.ISAAC.2021.73

DO - 10.4230/LIPICS.ISAAC.2021.73

M3 - Paper

SP - 73:1-73:16

T2 - 32nd International Symposium on Algorithms and Computation, ISAAC 2021

Y2 - 6 December 2021 through 8 December 2021

ER -