Monday, November 2, 2009
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
room 4.112
Lecture - 14:15
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
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.