Monday, May 19, 2008
Freie Universität Berlin
Institut für Informatik
Takustr. 9,
room 005
Lecture - 14:15
Abstract:
A unique sink orientation (USO) is an orientation of the n-cube graph with
the property that every subgraph induced by a nonempty cube face has a
unique sink. In particular, there is a unique global sink. In the talk,
I will first discuss USO in general: Where do they come from? What are their
combinatorial properties? Where are the algorithmic challenges?
In a second part, I will concentrate on specific families of USO. A family of USO is called regular if it can be described in a well-defined sense by a finite state transducer (nondeterministic finite automaton with output). Inituitively, this means that the family has a succint representation. To illustrate the concept, I will show that two well-known families of USO (by Klee & Minty, and by Morris) are regular.
In the last part, I will discuss the question whether families of USO
with a succint representation in the above sense are from an
algorithmic point of view "easier" than general families. I provide
some partial answers and conclude with a number of open questions.
Colloquium - 16:00
Abstract:
The Ham Sandwich Theorem states that any n continuous measures in
n-space can be split evenly with a single plane cut. More precisely:
given n continuous measures m_1,...,m_n in n-space, there exists an
affine hyperplane H that splits n-space into half-spaces H^+ and H^-
such that m_i(H^+)=1/2 for all i. If we replace 1/2 with some other
ratio, there exist continuous measures that cannot be split accordingly.
Can we nonetheless make some useful statement about when an uneven
splitting, i.e. a splitting according to some other fixed ratio, is
possible? This is the question we will discuss in this talk.