@incollection{GroetschelKrumkeRambauetal.2001, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg and Winter, Thomas and Zimmermann, Uwe}, title = {Combinatorial Online Optimization in Real Time}, booktitle = {Online Optimization of Large Scale Systems}, editor = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, publisher = {Springer}, pages = {679 -- 704}, year = {2001}, language = {en} } @incollection{GroetschelKrumkeRambau2001, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Online Optimization of Complex Transportation Systems}, booktitle = {Online Optimization of Large Scale Systems}, editor = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, publisher = {Springer}, pages = {705 -- 729}, year = {2001}, language = {en} } @article{GroetschelKrumkeRambauetal.2002, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg and Torres, Luis Miguel}, title = {Making the Yellow Angels Fly}, volume = {35}, journal = {SIAM News}, number = {4}, pages = {1,10,11}, year = {2002}, language = {en} } @article{GroetschelKrumkeRambau1999, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Wo bleibt der Aufzug?}, volume = {5}, journal = {OR News}, pages = {11 -- 13}, year = {1999}, language = {en} } @article{GroetschelKrumkeRambau2006, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Wo bleibt der Aufzug?}, volume = {Sonderausgabe}, journal = {OR News}, pages = {70 -- 72}, year = {2006}, language = {en} } @inproceedings{AscheuerGroetschelKrumkeetal.1999, author = {Ascheuer, Norbert and Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Combinatorial Online Optimization}, booktitle = {Operations Research Proceedings 1998. Selected Papers of the International Conference on Operations Research Zurich, August 31 - September 3, 1998}, editor = {Kall, Peter and L{\"u}thi, Hans-Jakob}, publisher = {Springer}, pages = {21 -- 37}, year = {1999}, language = {en} } @inproceedings{HeinzKrumkeMegowetal.2006, author = {Heinz, Stefan and Krumke, Sven and Megow, Nicole and Rambau, J{\"o}rg and Tuchscherer, Andreas and Vredeveld, Tjark}, title = {The Online Target Date Assignment Problem}, volume = {3879}, booktitle = {Proc. 3rd Workshop on Approximation and Online Algorithms}, editor = {Erlebach, Thomas and Persiano, Giuseppe}, publisher = {Springer}, pages = {230 -- 243}, year = {2006}, language = {en} } @inproceedings{HillerKrumkeSalibaetal.2009, author = {Hiller, Benjamin and Krumke, Sven and Saliba, Sleman and Tuchscherer, Andreas}, title = {Randomized Online Algorithms for Dynamic Multi-Period Routing Problems}, booktitle = {Proceedings of MAPSP}, pages = {71 -- 73}, year = {2009}, language = {en} } @inproceedings{HuelsermannJaegerPoensgenetal.2003, author = {H{\"u}lsermann, Ralf and J{\"a}ger, Monika and Poensgen, Diana and Krumke, Sven and Rambau, J{\"o}rg and Tuchscherer, Andreas}, title = {Dynamic routing algorithms in transparent optical networks}, booktitle = {Proceedings of the 7th IFIP Working Conference on Optical Network Design \& Modelling (ONDM 2003)}, editor = {Cinkler, Tibor and Jakab, Tivadar and Tapolcai, J{\`a}nos and G{\`a}sp{\`a}r, Csaba}, publisher = {Kluwer Academic Press}, pages = {293 -- 312}, year = {2003}, language = {en} } @misc{HillerKrumkeSalibaetal.2009, author = {Hiller, Benjamin and Krumke, Sven and Saliba, Sleman and Tuchscherer, Andreas}, title = {Randomized Online Algorithms for Dynamic Multi-Period Routing Problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11132}, number = {09-03}, year = {2009}, abstract = {The Dynamic Multi-Period Routing Problem DMPRP introduced by Angelelli et al. gives a model for a two-stage online-offline routing problem. At the beginning of each time period a set of customers becomes known. The customers need to be served either in the current time period or in the following. Postponed customers have to be served in the next time period. The decision whether to postpone a customer has to be done online. At the end of each time period, an optimal tour for the customers assigned to this period has to be computed and this computation can be done offline. The objective of the problem is to minimize the distance traveled over all planning periods assuming optimal routes for the customers selected in each period. We provide the first randomized online algorithms for the DMPRP which beat the known lower bounds for deterministic algorithms. For the special case of two planning periods we provide lower bounds on the competitive ratio of any randomized online algorithm against the oblivious adversary. We identify a randomized algorithm that achieves the optimal competitive ratio of \$\frac{1+\sqrt{2}}{2}\$ for two time periods on the real line. For three time periods, we give a randomized algorithm that is strictly better than any deterministic algorithm.}, language = {en} }