Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2010.2476
URN: urn:nbn:de:0030-drops-24766
URL: https://drops.dagstuhl.de/opus/volltexte/2010/2476/
Epstein, Leah ; Levin, Asaf ; Mestre, Julián ; Segev, Danny
Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model
| pdf-format: |
|
Abstract
We study the maximum weight matching problem in the semi-streamingmodel, and improve on the currently best one-pass algorithm due to
Zelke (Proc.\ STACS~'08, pages 669--680) by devising a deterministic
approach whose performance guarantee is $4.91 + \eps$. In addition,
we study {\em preemptive} online algorithms, a sub-class of one-pass
algorithms where we are only allowed to maintain a feasible matching
in memory at any point in time. All known results prior to Zelke's
belong to this sub-class. We provide a lower bound of $4.967$ on the
competitive ratio of any such deterministic algorithm, and hence
show that future improvements will have to store in memory a set of
edges which is not necessarily a feasible matching. We conclude by
presenting an empirical study, conducted in order to compare the
practical performance of our approach to that of previously
suggested algorithms.
BibTeX - Entry
@InProceedings{epstein_et_al:LIPIcs:2010:2476,
author = {Leah Epstein and Asaf Levin and Juli{\'a}n Mestre and Danny Segev},
title = {{Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model}},
booktitle = {27th International Symposium on Theoretical Aspects of Computer Science},
pages = {347--358},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-16-3},
ISSN = {1868-8969},
year = {2010},
volume = {5},
editor = {Jean-Yves Marion and Thomas Schwentick},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2476},
URN = {urn:nbn:de:0030-drops-24766},
doi = {10.4230/LIPIcs.STACS.2010.2476},
annote = {Keywords: Approximation guarantees, semi-streaming model, one-pass algorithm}
}
| Keywords: | Approximation guarantees, semi-streaming model, one-pass algorithm | |
| Seminar: | 27th International Symposium on Theoretical Aspects of Computer Science | |
| Issue date: | 2010 | |
| Date of publication: | 09.03.2010 |
