[home] - [up]


Lectures and Colloquia during the semester



January 27, 2003

Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 042           - map -
Lecture - 14:15

Stefan Felsner - Freie Universität Berlin

Lattice Structures from Planar Graphs

Abstract: The set of all orientations of a planar graph with prescribed outdegrees carries the structure of a distributive lattice. We indicate the main steps of the proof.

Based on this result it can be shown that several interesting combinatorial sets related to a planar graph have a lattice structure: Eulerian orientations, spanning trees and Schnyder woods. For the Schnyder wood application some additional theory has to be developed. In particular it is shown that a Schnyder wood for a planar graph induces a Schnyder wood for the dual.


Colloquium - 16:00

Nicole Megow - Technische Universität Berlin

Deterministic on-line scheduling on parallel machines

Abstract: We consider the on-line scheduling problem of minimizing the total weighted completion time on parallel machines subject to release dates. Extending Smith's ratio rule, we present a simple deterministic on-line algorithm with a competitive ratio of precisely 2 for the preemptive setting. This result significantly improves the currently best known result for that problem. The proof is established using a new lower bound on the optimal objective value. Moreover, we present two 4-competitive algorithms for the same problem in the non-preemptive setting. While one of them uses a conversion technique, the other one applies a waiting strategy in order to cope with non-preemption. We obtain only a slight improvement in the performance compared to the current best known result, but our algorithms and their analysis are much simpler if we apply the new lower bound.


[home] - [up] - [top]