Improved Weighted Matching in the Sliding Window Model

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

3 Citations (Scopus)

Abstract

We consider the Maximum-weight 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 maximum-weight 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 state-of-the-art 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 O˜(n).
Original languageEnglish
Title of host publicationSTACS 2023
Subtitle of host publication40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023
EditorsPetra Berenbrink, Patricia Bouyer, Anuj Dawar, Mamadou Moustapha Kante
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages6:1-6:21
Volume254
ISBN (Electronic)9783959772662
DOIs
Publication statusPublished - 3 Mar 2023
Event40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
- Universität Hamburg, Hamburg, Germany
Duration: 7 Mar 20239 Mar 2023
https://www.conferences.uni-hamburg.de/event/272/

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume254
ISSN (Print)1868-8969

Conference

Conference40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Country/TerritoryGermany
CityHamburg
Period7/03/239/03/23
Internet address

Bibliographical note

Funding Information:
Funding Cezar-Mihail Alexandru: Supported by EPSRC DTP studentship EP/T517872/1. Pavel Dvořák: Supported by EPSRC New Investigator Award EP/V010611/1 and by Czech Science Foundation GAČR grant #22-14872O. Christian Konrad: Supported by EPSRC New Investigator Award EP/V010611/1. Kheeran K. Naidu: Supported by EPSRC DTP studentship EP/T517872/1.

Publisher Copyright:
© Cezar-Mihail Alexandru, Pavel Dvořák, Christian Konrad, and Kheeran K. Naidu.

Fingerprint

Dive into the research topics of 'Improved Weighted Matching in the Sliding Window Model'. Together they form a unique fingerprint.

Cite this