Weighted matching in the semi-streaming model (Q2428674): Difference between revisions

A simple algorithm for the maximum weight matching problem is analysed. The \(m\) edges of the input graph on \(n\) vertices are given one by one and carry positive weights. The local memory consists of \(O(n\log n)\) bits; see [\textit{S. Muthukrishnan}, Found. Trends Theor. Comput. Sci. 1, No. 2, 126~p.\ (2005; Zbl 1143.68385)] for this model. The algorithm maintains an initially empty matching \(M\) consisting of edges known so far and remembers for each edge in \(M\), up to two, shadow edges it displaced from \(M\). For a new edge \(e\) let \(A\) be the set that consist of \(e\), its potential shadow edges, and their shadow edges. To handle \(e\), \(M \cap A\) is replaced by a maximum weight subset of \(A\) that forms a matching. This gives an approximation ratio of \(5.58\). \textit{L. Epstein} et al. [SIAM J. Discrete Math. 25, No. 3, 1251--1265 (2011; Zbl 1237.05163)] achieve \(4.91+\varepsilon\).