Weighted matching in the semi-streaming model (Q2428674): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 21:02, 2 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Weighted matching in the semi-streaming model |
scientific article |
Statements
Weighted matching in the semi-streaming model (English)
0 references
26 April 2012
0 references
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\).
0 references
semi-streaming algorithm
0 references
approximation algorithm
0 references
matching
0 references
graph algorithm
0 references