Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, May 6, 2013

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005

Lecture - 14:15

Bernd Gärtner - ETH Zürich

The Linear Complementarity Problem: An Advertisement

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

Andrei Asinowski - Freie Universität Berlin

The "even part" of Baxter permutations

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.

Letzte Aktualisierung: 30.04.2013