Invited Session Fri.3.H 3012

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

Cluster 2: Combinatorial optimization [...]

Graph optimization problems in the streaming model


Chair: Anand Srivastav



Friday, 15:15 - 15:40 h, Room: H 3012, Talk 1

Christian Konrad
On the order of graph streams


While classical graph algorithms assume random access to the input graph, a semi-streaming algorithm receives a sequence of edges of the input graph and processes them one-by-one in sequential order while using small memory. How important is the order in which the edges arrive? Are there problems that become easier if we assume that edges arrive in uniform random order instead of worst-case order? Are there other particular orders that make sense to consider?
We address these questions via two concrete examples: the unweighted bipartite graph matching problem and the unweighted semi-matching problem: given a bipartite graph (A, B, E), in the semi-matching problem we aim to match all A vertices to B vertices such that the maximal degree of the B vertices is minimized.
The talk concludes with a review on open problems in this area of research.



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

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.



Friday, 16:15 - 16:40 h, Room: H 3012, Talk 3

Mariano Zelke
Algorithmic techniques for data stream computations


For computation on today's massive data, it is not reasonable anymore to assume the existence of a main memory containing the whole input for fast random access. On such data streaming algorithms are appropriate for which fast random access to the input and even its complete storage are dispensable. In contrast, the input is processed in an online fashion using a main memory size that significantly falls below the input data size.
In this talk we present some basic techniques for streaming algorithms which provide the foundation for more elaborate approaches. We illustrate reservior sampling to draw uniform random samples out of a stream of unknown length and sliding window sampling to exclude outdated input items from the sample. Moreover, we show how to approximate the frequency moments of a stream via the technique of AMS sampling and how to estimate the multiplicity of an item in the input stream by using the count-min sketch.


  In particular, Texas Loans Online can cater to the needs of its residents. 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.