#
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

*Abstract:*

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

*Abstract:*

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