Weighted Matching in the Semi-Streaming Model
Mariano Zelke · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2008
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.