Weighted Matching in the Semi‐Streaming Model

We present an approximation algorithm to find a weighted matching of a graph in the one‐pass semi‐streaming model. The semi‐streaming model forbids random access to the input graph and restricts the memory to $𝒪(n\cdot polylogn)$ bits where n denotes the number of the vertices of the input graph. We obtain an approximation ratio of 5.58 while the previously best algorithm achieves a ratio of 5.82.