A (2+ε)-Approximation for Maximum Weight Matching in the Semi-Streaming Model
classification
💻 cs.DS
keywords
epsilonapproximationmodelsemi-streamingalgorithmmatchingmaximumweight
Add this Pith Number to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{E57SRGT7}
Prints a linked pith:E57SRGT7 badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original abstract
We present a simple deterministic single-pass $(2+\epsilon)$-approximation algorithm for the maximum weight matching problem in the semi-streaming model. This improves upon the currently best known approximation ratio of $(4+\epsilon)$. Our algorithm uses $O(n\log^2 n)$ bits of space for constant values of $\epsilon$. It relies on a variation of the local-ratio theorem, which may be of use for other algorithms in the semi-streaming model as well.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.