TY - GEN A1 - Hauptmeier, Dietrich A1 - Krumke, Sven A1 - Rambau, Jörg T1 - The Online Dial-a-Ride Problem under Reasonable Load N2 - In this paper, we analyze algorithms for the online dial-a-ride problem with request sets that fulfill a certain worst-case restriction: roughly speaking, a set of requests for the online dial-a-ride problem is reasonable if the requests that come up in a sufficiently large time period can be served in a time period of at most the same length. This new notion is a stability criterion implying that the system is not overloaded. The new concept is used to analyze the online dial-a-ride problem for the minimization of the maximal resp.\ average flow time. Under reasonable load it is possible to distinguish the performance of two particular algorithms for this problem, which seems to be impossible by means of classical competitive analysis. T3 - ZIB-Report - SC-99-08 KW - online optimization KW - competitive analysis KW - elevator Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3961 ER - TY - GEN A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg A1 - Winter, Thomas A1 - Zimmermann, Uwe T1 - Combinatorial Online Optimization in Real Time N2 - Optimization is the task of finding an optimum solution to a given problem. When the decision variables are discrete we speak of a combinatorial optimization problem. Such a problem is online when decisions have to be made before all data of the problem are known. And we speak of a real-time online problem when online decisions have to be computed within very tight time bounds. This paper surveys the are of combinatorial online and real-time optimization, it discusses, in particular, the concepts with which online and real-time algorithms can be analyzed. T3 - ZIB-Report - 01-16 KW - Online Optimization KW - Realtime Optimization KW - Competitive Analysis KW - Heuristics KW - Survey Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6424 ER -