**Friday, 15:45 - 16:10 h, Room: H 3012**

**Lasse Kliemann**

*(1+1/k)*-Approximate maximum matching in bipartite graph streams in *O(k*^{5}) passes and improvements

**Coauthors: Sebastian Eggert, Peter Munstermann, Anand Srivastav**

**Abstract:**

Two algorithms for the *maximum matching* problem in

*bipartite graph streams* will be presented. RAM is

restricted to *O(n)* edges at a time, *n* denoting the number of

vertices. Given a parameter *k*, we find a *(1+1/k)*

approximation. The *number of passes* is allowed to depend

on *k*. When the number of passes is independent of *n*, we

speak of a *semi-streaming algorithm*.

The first algorithm is a semi-streaming algorithm requiring only

*O(k*^{5}) passes. It was developed and analyzed purely

theoretically. The second algorithm was developed by means of

Algorithm Engineering. It was proven to have the same

approximation guarantee as the first one - but in the worst case

it can require a linear (in *n*) number of passes. Hence it is

no semi-streaming algorithm. However, on a large set of test

instances it outperformed the first algorithm by an impressive

margin: for a 90*%* approximation (*k=9*) the second algorithm

never required more than 94 passes, while the first one

required up to 32,000. But even those 32,000 are far away

from the theoretical *O(k*^{5}) bound.

Talk 2 of the invited session Fri.3.H 3012

**"Graph optimization problems in the streaming model"** [...]

Cluster 2

**"Combinatorial optimization"** [...]