Simplified and Space-Optimal Semi-Streaming (2+epsilon)-Approximate Matching
OPEN ACCESS
Loading...
Author / Producer
Date
2019
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
In a recent breakthrough, Paz and Schwartzman (SODA'17) presented a single-pass (2+epsilon)-approximation algorithm for the maximum weight matching problem in the semi-streaming model. Their algorithm uses O(n log^2 n) bits of space, for any constant epsilon>0. We present a simplified and more intuitive primal-dual analysis, for essentially the same algorithm, which also improves the space complexity to the optimal bound of O(n log n) bits - this is optimal as the output matching requires Omega(n log n) bits.
Permanent link
Publication status
published
External links
Book title
2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Journal / series
Volume
69
Pages / Article No.
13
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Streaming; Semi-Streaming; Space-Optimal; Matching
Organisational unit
09587 - Ghaffari, Mohsen (ehemalig) / Ghaffari, Mohsen (former)