Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Scheduling problems with stochastic processing times are combinatorial optimization problems with sometimes counterintuitive phenomena. For example, optimal solutions might even require to deliberately leave capacity unused. The talk gives a brief introduction into the model. It turns out that much of the work that has been done for non-stochastic problems can - with some extra work - be carried over to the more general stochastic setting. That leads to approximation algorithms which have performance guarantees that depend quadratically on the coefficient of variation of the underlying random variables. The talk will give one such example, namely an LP-based approximation algorithm for unrelated machine scheduling. However to design constant-factor approximation algorithms -or prove this is impossible- remains a major open problem. Some recent progress in this direction will be highlighted, too. (The talk is largely based on joint work with Skutella and Sviridenko.)

Professor Marc Uetz is the Chair for Discrete Mathematics and Mathematical Programming at the University of Twente, Netherlands. He received his Ph.D. in 2001 from TU Berlin under the direction of Rolf Möhring.