Many optimization problem exhibit a modular structure and decompose into smaller units. Algorithms and analytic tools for the evaluation of individual models have been succesfully investigated. However, little is known about the interplay of heterogenous modules in complex systems.
The goal of the project is to exploit the structure of modular real-time(online) systems in order to develop concepts for the mathematical evaluation of composed algorithms. A key question in this context is, whether and when a performance guarantee for all the (comparatively simple) modules does ensure a good behavior of the whole (complex) system. We focus on combinatorial optimization problems arising in transportation and logistics. To substantiate our
Publications
- N. Megow, M. Uetz, T. Vredeveld. Stochastic Online Scheduling on Parallel Machines. In: Proceedings of the 2nd Workshop on Approximation and Online Algorithms, 2004. To appear.
- M. B. Barz. Verteilte Algorithmen Zur Dynamischen Konfiguration Optischer Netze. Master's Thesis, Technische Universität Berlin, 2004. (in German).
- I. Dischke. Disposition von Einsatzfahrzeugen: Startheuristiken, Branching-Regeln und Rundungstechniken. Master's Thesis, Technische Universität Berlin, 2004. (in German).
- S. Westphal. Lower Bounds and Quality Guarantees for Online-Dispatching. Master's Thesis, Technische Universität Berlin, 2004.
- S. O. Krumke, N. Megow, T. Vredeveld. How to Whack Moles. In: Proceedings of the 1st Workshop on Approximation and Online Algorithms, pp. 192–205, 2004.
- L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, G. Schäfer, T. Vredeveld. Average Case and Smoothed Competitive Analysis for the Multi-Level Feedback Algorithm. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 462–471, 2003.
- A. Coja-Oghlan, S. O. Krumke, T. Nierhoff. Scheduling a server on a caterpillar network - a probabilistic analysis. In: Proceedings of the 6th Workshop on Models and Algorithms for Planning and Scheduling Problems, pp. 48–50, 2003. Available as ZIB-Report 03-12, 2003.
- A. Coja-Oghlan, S. O. Krumke, T. Nierhoff. A heuristic for the Stacker Crane Problem on trees which is almost surely exact. In: Proceedings of the 14th International Symposium on Algorithms and Computation, 2003. To appear.
- R. Hülsermann, M. Jäger, S. O. Krumke, D. Poensgen, J. Rambau, A. Tuchscherer. Experimental Study of Routing Algorithms in Optical Networks. In: Proceedings of the 7th IFIP Working Conference on Optical Network Design & Modelling, 2003. to appear.
- D. Hauptmeier, S. O. Krumke, J. Rambau. The Online Dial-a-Ride Problem under Reasonable Load. Theoretical Computer Science, , 2002.
- Martin Grötschel, Sven O. Krumke, Jörg Rambau. Online Optimization of Complex Transportation Systems. In: Online Optimization of Large Scale Systems, Martin Grötschel and Sven O. Krumke and Jörg Rambau (Eds.), pp. 705–729, Springer, 2001.
- Online Optimization of Large Scale Systems. Springer, Berlin Heidelberg New York, 2001.
- Martin Grötschel, Sven O. Krumke, Jörg Rambau, Thomas Winter, Uwe T. Zimmermann. Combinatorial Online Optimization in Real Time. In: Online Optimization of Large Scale Systems, Martin Grötschel and Sven O. Krumke and Jörg Rambau (Eds.), pp. 679–704, Springer, 2001.
Partners
DFG Research Center Matheon
Project B8
Project C5
Project C6
Sensitivity
and Robustness in Combinatorial Online Optimization
Project C7
eCom-Logistik
Falkensee (Mr. Eckle)
Hermes Technischer Kundendienst GmbH & Co. KG (Frank Hinsch)
Allgemeiner Deutscher Automobilclub (Renate Ahlers)
Intergraph Public Safety (Sebastian Stepfer)