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" [...]


  The deal is that Payday Loans Indiana online can save your time, nerves and make a solution of all your financial problems. Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.