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, February 4, 2013

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

Lecture - 14:15

Günter Rote - Freie Universität Berlin

Algorithms for isotonic regression

In isotonic regression, we want to approximate given sequence of numbers a1,..., an by numbers x1,x2,...,xn subject to constraints of the form x_i<=x_j, for certain pairs (i,j).

The objective is to minimize some error based on the deviations |x_i-a_i|, typically the L1, L2 or Lmax norm, possibly with weights. The simplest case is when x1,x2,...,xn is required to be an increasing sequence, but other types of orders have been considered: tree-like orders, orders given by an arbitrary directed acyclic graph, d-dimensional orders, or d-dimensional arrays.

1. I will describe the classical Pool Adjacent Violators (PAV) method, which has been extensively studied.
2. I will describe a simple dynamic programming approach for the linearly ordered case, which leads to a quite general and versatile method, also for the related bitonic regressen problem.
3. I will point out the relation to minimum-cost flows.
4. I will finally describe a randomized method for d-dimensional orders, which improves previous methods and uses less space.

It is based on a general optimization technique of Timothy Chan.

Colloquium - 16:00

Rafel Jaume - Freie Universität Berlin

The finest regular coarsening of a polyhedral subdivision

A notion of relaxation for an incompatible system of linear homogeneous inequalities is introduced. We show that the minimal subset of inequalities that must be relaxed in order the system to be compatible is well defined. This result is used to show that the finest regular coarsening of a polyhedral subdivision and its regularity poset are also well defined. Some properties of these objects are derived, which confer structure on the set of non-regular subdivisions of a given point set. The class of recursively-regular subdivisions is defined. We show that given a point set, its recursively-regular subdivisions are a superset of its regular subdivisions and a subset of its visibility-acyclic subdivisions.

Joint work with Günter Rote.

Letzte Aktualisierung: 29.01.2013