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


Lasse Kliemann
(1+1/k)-Approximate maximum matching in bipartite graph streams in O(k5) passes and improvements

Coauthors: Sebastian Eggert, Peter Munstermann, Anand Srivastav


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(k5) 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(k5) bound.


Talk 2 of the invited session Fri.3.H 3012
"Graph optimization problems in the streaming model" [...]
Cluster 2
"Combinatorial optimization" [...]


  payday loans direct . But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.