## 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

**Abstract:**

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(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.

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

**Mariano Zelke**

Algorithmic techniques for data stream computations

**Abstract:**

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.