[home] - [up] |
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
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.