Combinatorial Online Planning
Many problems are naturally online problems. They require decisions to be made on the basis of incomplete data. In online optimization the input is modelled as a (finite) sequence of requests which are given step-by-step to an online algorithm. After a request becomes known, the online algorithm must make a decision without information about future requests. Depending on the specific problem, the decisions of the algorithm might be further constrained.
The goal of this project is to obtain new results for the construction and analysis of online algorithms. We want to overcome the weaknesses of competitive analysis (the "standard tool" for theoretical analysis of online algorithms), which is often overly pessimistic.
Publikationen
2008
2005
2004
2002
2001
2000
1999
2008 |
|||
Benjamin Hiller, Tjark Vredeveld | Probabilistic analysis of Online Bin Coloring algorithms via Stochastic Comparison | ZIB-Report 08-18 (Appeared in: Proceedings of the 16th Annual European Symposium on Algorithms, ESA 2008. Springer 2008. Lecture Notes in Computer Science, 5193, pp. 528-539) |
PDF
BibTeX URN |
2005 |
|||
Benjamin Hiller | Probabilistic Competitive Analysis of a Dial-a-Ride Problem on Trees Under High Load | ZIB-Report 05-56 |
PDF
BibTeX URN |
2004 |
|||
Benjamin Hiller | Bad Guys are Rare: Probabilistic Analysis of an Elementary Dial-a-Ride Problem | Master's thesis, TU Ilmenau, 2004 |
PDF
BibTeX URN |
2002 |
|||
Sven Krumke, Luigi Laura, Maarten Lipmann, Alberto Marchetti-Spaccamela, Willem de Paepe, Diana Poensgen, Leen Stougie | Non-Abusiveness Helps: An O(1)-Competitive Algorithm for Minimizing the Maximum Flow Time in the Online Traveling Salesman Problem | ZIB-Report 02-36 (Appeared in: Proc. of the 5th Int. Workshop on Approximation Algorithms for Combinatorial Optimization. Springer 2002. LNCS, 2462, pp. 200-214) |
PDF
BibTeX URN |
Sven Krumke, Diana Poensgen | Online Call Admission in Optical Networks with Larger Wavelength Demands | ZIB-Report 02-22 (Appeared in: Graph-Theoretic Concepts in Computer Science. 28 Intern. Workshop, WG 2002, Cesky Krumlov, Czech Republic, June 13-15, 2002, revised papers. L. Kucera (ed.) Springer 2002. LNCS 2573. Pp. 333-344) |
PDF
BibTeX URN |
Sven Krumke | Online Optimization: Competitive Analysis and Beyond | Habilitation, 2002 |
PDF
BibTeX URN |
2001 |
|||
Sven Krumke, Willem de Paepe, Jörg Rambau, Leen Stougie | Online Bin-Coloring | ZIB-Report 01-07 (Appeared in: Proc. of the 9th European Symposium on Algorithms, Springer 2001, LNCS 2161, pp. 74-84) |
PDF
BibTeX URN |
2000 |
|||
Sven Krumke | News from the Online Traveling Repairman | ZIB-Report 00-08 (A rev. vers. - together with W. E. de Paepe and D. Poensgen - appeared in: Proc. of the 26th Int. Symp. on Math. Foundations of Computer Science, Springer 2001, LNCS, 2136, pp. 487-499 and in Theoretical Computer Sceince 295 (2003 pp. 279-294) |
PDF
BibTeX URN |
1999 |
|||
Dietrich Hauptmeier, Sven Krumke, Jörg Rambau, Hans-Christoph Wirth. | Euler is Standing in Line | ZIB-Report SC-99-06 (Appeared in: Discrete Appl. Math. 113 (2001) 87-107. A prel. vers. appeared in: Proc. of the 25nd Intern. Workshop on Graph-Theoretic Concepts in Computer Science (WG'99), Lecture Notes in Computer Science, vol. 1665, Springer (1999) 42-54) |
PDF
BibTeX URN |