Monday, May 6, 2013
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
A linear complementarity problem (LCP) looks like a linear program,
except that the variables come in pairs, and a solution must have at
least one variable from each pair equal to zero. It is NP-complete to
decide whether an LCP has a solution, but there is an important special
case whose complexity status is unresolved: the P-matrix LCP. In this
talk, I want to advertise this interesting problem and a natural
combinatorial abstraction of it: unique sink orientations (USO). I will
present a new polynomial-time algorithm for K-matrix LCP (a well-studied
subclass of P-matrix LCP) as well as the first polynomial-time algorithm for
P-matrix LCP with tridiagonal matrices. Both algorithms are purely based
on simple combinatorial properties of the underlying USOs. This is joint work
with Jan Foniok, Komei Fukuda, Hans-Jakob Lüthi and Markus Sprecher.
Colloquium - 16:00
Abstract:
Baxter permutations are usually defined as (2-41-3, 3-14-2)-avoiding
permutations, but in fact these are so-called "reduced" Baxter
permutations. According to the original definition, a [complete] Baxter
permutation is a permutation of [2n-1] that satisfies certain conditions,
one of them being the following: the odd numbers are mapped into the odd
numbers, and the even numbers are mapped into the even numbers. This allows
to split a complete Baxter permutation of size 2n-1 into two parts: the
"odd part" of size n, and the "even part" of size n-1. One of the
properties of Baxer permutations is that the "even part" is completely
determined by the "odd part".
In these terms, the reduced Baxter permutations are precisely the
permutations that can be obtained as the "odd part" of complete Baxter
permutations. This family is well-studied, and many combinatorial
interpretations are known.
In this work we study the family of permutations that can be obtained as
the "even part" of complete Baxter permutations. Our results include:
characterization of the family by forbidden patterns; characterization of
reduced Baxter permutations that correspond to the same "even part";
enumeration; and some combinatorial interpretations.
A joint work with G. Barequet, M. Bousquet-Mélou, T. Mansour, and R.Y.
Pinter.