#
Monday Lecture and Colloquium

**Monday, November 2, 2009 **

Humboldt-Universität zu Berlin

Institut für Informatik

Rudower Chaussee 25

12489 Berlin

room 4.112

** Lecture - 14:15**

###
Anand Srivastav - Universität Kiel

### Bipartite Graph Matchings in the Semi-Streaming Model

*Abstract:*

We give an overwiew on matching
in graphs and hypergraphs in the usual RAM model and then concentrate on
a new algorithm for finding a large matching in a
bipartite graph in the semi-streaming model. In this model, the
input graph $G=(V, E)$ is represented as a stream of its edges in
some arbitrary order, and storage of the algorithm is bounded by
$O(n\ {\rm polylog} n)$ bits, where $n = |V|$. For $\epsilon > 0$, our
algorithm finds a $1/(1+\epsilon)$-approximation of a maximum-
cardinality matching and uses $1/\epsilon^8$ passes over the input
stream. The only previously known algorithm with such
arbitrarily good approximation requires $\Omega(1/\epsilon^{1/\epsilon})$ passes
(McGregor 2005).

Keywords: bipartite graph matching, streaming algorithms,
approximation algorithms

Joint Work with: Lasse Kliemann and Sebastian Eggert (Kiel)

**Colloquium - 16:00**

###
Berit Grußien - Humboldt Universität Berlin

###
Polynomial-Time Algorithms for Constraint Satisfaction Problems

*Abstract:*

Constraint satisfaction problems naturally arise in form of
combinatorial problems in artificial intelligence, computational
linguistics, scheduling, and many more areas of computer science. An
instance of a constraint satisfaction problem (CSP) consists of a
finite set of variables *V*, a (finite) domain *D* of values for the
variables, and a set *C* of constraints that are imposed on the
variables to restrict the values they can be assigned to. The task is
to decide whether there is an assignment of values to the variables,
such that all constraints are satisfied. In its full generality the
constraint satisfaction problem is NP-complete. To find subclasses that
are polynomial-time tractable it proved to be useful to restrict the
types of constraints that may be expressed by allowing only constraint
relations from a fixed finite set - the constraint language.
Such problems are called non-uniform CSPs.
This talk will focus on known tractable non-uniform CSPs and the
algorithms that underlie the tractability results. I present the
principles and runtimes of the algorithms. Further, we look at some
simple algorithms from the algebraic point of view, and for each
algorithm an algebraic characterization of the constraint languages
tractable by the algorithm is presented, which is joint work with Hubie
Chen and Víctor Dalmau.

Letzte Aktualisierung:
23.10.2009