Rolf H. Möhring -Technische Universität Berlin

Coping with Uncertainty in Scheduling

Abstract: Combinatorial optimizers have recently become more aware about the influence of uncertainty and randomness in solving combinatorial optimization problems. This lecture will survey three different approaches how to cope with these phenomena in the context of scheduling: (1) online optimization and competitive analysis, (2) stochastic dynamic optimization with expected performance and expected competitive ratio, respectively, and (3) stochastic linear programming. Particular emphasis will be given to the "LP-based approach" for stochastic scheduling problems which currently seems to be the most far-reaching general technique for obtaining performance guarantees.

Colloquium - 16:00

Maike Walther -Freie Universität Berlin

Discrete Approximation of the Frechet Distance

Abstract: The Frechet Distance is a metric for parametrised geometric objects such as curves and surfaces. For curves it can be computed in polynomial time. For higher dimensional objects, deciding whether the Frechet Distance is less than a given value is NP-hard. We investigate the computability in the case of surfaces by a discrete approximation. For this purpose, we consider the approximation of homeomorphisms on the unit square by simplicial maps and vice versa.