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).
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 language | English |
---|---|
Title of host publication | STACS 2023 |
Subtitle of host publication | 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023 |
Editors | Petra Berenbrink, Patricia Bouyer, Anuj Dawar, Mamadou Moustapha Kante |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Pages | 6:1-6:21 |
Volume | 254 |
ISBN (Electronic) | 9783959772662 |
DOIs | |
Publication status | Published - 3 Mar 2023 |
Event | 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) - Universität Hamburg, Hamburg, Germany Duration: 7 Mar 2023 → 9 Mar 2023 https://www.conferences.uni-hamburg.de/event/272/ |
Publication series
Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 254 |
ISSN (Print) | 1868-8969 |
Conference
Conference | 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) |
---|---|
Country/Territory | Germany |
City | Hamburg |
Period | 7/03/23 → 9/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.