Readers with a particularly long memory may recall that we’re in the midst of a series of “bite-sized results” in data stream algorithms. Back in October, we discussed graph spanners and now it’s time for some graph matchings.

So consider a stream of undirected weighted edges where is the weight of edge . Can we find a matching, i.e., a subset of the edges that don’t share any endpoints, such that the sum of the associated weights is maximized?

Here’s a really simple algorithm that maintains a matching as the edges are processed:

- The initial matching is the empty matching
- When processing edge , the weight of is compared with the total weight of the conflicting edges, i.e., the edges in the currently stored matching that share an endpoint with . If then is added to the matching and the conflicting edges are removed.

It makes a nice exercise to prove that the above algorithm achieves a approximation ratio (see pages 149 and 150 of this thing if you get stuck) and choosing the optimal gives you a 5.828 approximation. Incidentally, this algorithm later found use in a paper on auctioning ad slots [Constantin, Feldman, Muthukrishnan, Pal].

Subsequently, a 5.585 approximation algorithm was presented in [Zelke]. The main idea was to remember some of the edges that were ejected from the matching in the second step of the above algorithm. These edges are potentially added back into the matching at some later point. While a natural idea, it requires substantially more analysis to show the improved approximation ratio.

### Like this:

Like Loading...

*Related*

## 3 comments

Comments feed for this article

February 22, 2010 at 10:43 am

DanuFYI, Zelke’s 5.828-approximation algorithm was recently improved by Epstein etal. (STACS’10) to 4.91 (http://arxiv.org/abs/0907.0305). The algorithm and analysis is quite simple.

February 22, 2010 at 10:54 am

AndrewThanks Danu! I was planning to give the Epstein et al. result in Part 2. I also really like their result separating the semi-streaming and preemptive-online model.

March 17, 2010 at 6:02 am

Bite-sized streams: Graph Matchings (Part 2) « the polylogblog[...] 17, 2010 in educational | by Andrew Following on from the last post on maximum weighted matchings in the stream model, I wanted to briefly mention a result that appeared in STACS last week. The set-up is the same as [...]