We reduce the best known approximation ratio for finding a weighted matching of a graph using a one-pass semi-streaming algorithm from 5.828 to 5.585. The semi-streaming model forbids random access to the input and restricts the memory to $mathcal{O(ncdotmbox{polylog,n)$ bits. It was introduced by Muthukrishnan in 2003 and is appropriate when dealing with massive graphs.
@InProceedings{zelke:LIPIcs.STACS.2008.1312, author = {Zelke, Mariano}, title = {{Weighted Matching in the Semi-Streaming Model}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {669--680}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1312}, URN = {urn:nbn:de:0030-drops-13128}, doi = {10.4230/LIPIcs.STACS.2008.1312}, annote = {Keywords: Semi-streaming algorithm, matching, approximation algorithm, graph algorithm} }
Feedback for Dagstuhl Publishing