TY - GEN A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg T1 - Wo bleibt der Aufzug? N2 - Dieser Artikel gibt eine allgemeinverständliche Einführung in die spezielle Problematik kombinatorischer Online-Problem am Beispiel der Fahrstuhlsteuerung. T3 - ZIB-Report - SC-99-29 KW - Aufzugsteuerung KW - Online-Optimierung KW - Echtzeit-Optimierung KW - kompetitive Analyse Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4175 ER - TY - JOUR A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg T1 - Wo bleibt der Aufzug? JF - OR News Y1 - 1999 VL - 5 SP - 11 EP - 13 ER - TY - JOUR A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg T1 - Wo bleibt der Aufzug? JF - OR News Y1 - 2006 VL - Sonderausgabe SP - 70 EP - 72 ER - TY - GEN A1 - Rambau, Jörg T1 - Triangulierungen von Punktmengen und Polyedern N2 - Dieser Report wurde im Sommersemester 2000 an der TU Berlin in einer Spezialvorlesung über Triangulierungen von Punktmengen und Polyedern als Skriptum verwendet. Nach einem motivierenden Kapitel werden grundlegende Begriffe und Konstruktionen in der Theorie der Triangulierungen von Punktmengen und Polyedern vorgestellt. Danach werden als weiterführende Themen reguläre Triangulierungen, Sekundärpolytope, bistellare Operationen, höhere Stasheff-Tamari-Halbordnungen und Triangulierungen mit wenigen bzw. gar keinen Flips behandelt. Ein Kapitel über Enumeration und Optimierung beschließt die Zusammenstellung. T3 - ZIB-Report - 00-46 KW - point configuration KW - triangulation KW - polytope KW - polyhedron KW - Gale diagram KW - secondary polytope KW - cyclic polytope KW - graph of all triangulations KW - conn Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6145 ER - TY - GEN A1 - Rambau, Jörg T1 - TOPCOM: Triangulations of Point Configurations and Oriented Matroids N2 - TOPCOM is a package for computing triangulations of point configurations and oriented matroids. For example, for a point configuration one can compute the chirotope, components of the flip graph of triangulations, enumerate all triangulations. The core algorithms implemented in TOPCOM are described, and implentation issues are discussed. T3 - ZIB-Report - 02-17 KW - triangulation KW - point configuration KW - oriented matroid KW - software KW - chirotope KW - circuit KW - cocircuit KW - symmetry KW - TOPCOM Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6849 ER - TY - GEN A1 - Ascheuer, Norbert A1 - Krumke, Sven A1 - Rambau, Jörg T1 - The Online Transportation Problem: Competitive Scheduling of Elevators N2 - In this paper we consider the following online transportation problem (\textsc{Oltp}): Objects are to be transported between the vertices of a given graph. Transportation requests arrive online, specifying the objects to be transported and the corresponding source and target vertex. These requests are to be handled by a server which commences its work at a designated origin vertex and which picks up and drops objects at their starts and destinations. After the end of its service the server returns to its start. The goal of \textsc{Oltp} is to come up with a transportation schedule for the server which finishes as early as possible. We first show a lower bound of~$5/3$ for the competitive ratio of any deterministic algorithm. We then analyze two simple and natural strategies which we call \textsf{REPLAN} and \textsf{IGNORE}. \textsf{REPLAN} completely discards its schedule and recomputes a new one when a new request arrives. \textsf{IGNORE} always runs a (locally optimal) schedule for a set of known requests and ignores all new requests until this schedule is completed. We show that both strategies, \textsf{REPLAN} and \textsf{IGNORE}, are $5/2$-competitive. We also present a somewhat less natural strategy \textsf{SLEEP}, which in contrast to the other two strategies may leave the server idle from time to time although unserved requests are known. We also establish a competitive ratio of~$5/2$ for the algorithm \textsf{SLEEP}. Our results are extended to the case of ``open schedules'' where the server is not required to return to its start position at the end of its service. T3 - ZIB-Report - SC-98-34 KW - online optimization KW - competitive analysis KW - elevator Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3779 ER - TY - GEN A1 - Heinz, Stefan A1 - Krumke, Sven A1 - Megow, Nicole A1 - Rambau, Jörg A1 - Tuchscherer, Andreas A1 - Vredeveld, Tjark T1 - The Online Target Date Assignment Problem N2 - Many online problems encountered in real-life involve a two-stage decision process: upon arrival of a new request, an irrevocable first-stage decision (the assignment of a specific resource to the request) must be made immediately, while in a second stage process, certain ``subinstances'' (that is, the instances of all requests assigned to a particular resource) can be solved to optimality (offline) later. We introduce the novel concept of an \emph{Online Target Date Assignment Problem} (\textsc{OnlineTDAP}) as a general framework for online problems with this nature. Requests for the \textsc{OnlineTDAP} become known at certain dates. An online algorithm has to assign a target date to each request, specifying on which date the request should be processed (e.\,g., an appointment with a customer for a washing machine repair). The cost at a target date is given by the \emph{downstream cost}, the optimal cost of processing all requests at that date w.\,r.\,t.\ some fixed downstream offline optimization problem (e.\,g., the cost of an optimal dispatch for service technicians). We provide general competitive algorithms for the \textsc{OnlineTDAP} independently of the particular downstream problem, when the overall objective is to minimize either the sum or the maximum of all downstream costs. As the first basic examples, we analyze the competitive ratios of our algorithms for the par ticular academic downstream problems of bin-packing, nonpreemptive scheduling on identical parallel machines, and routing a traveling salesman. T3 - ZIB-Report - 05-61 KW - Online Algorithms KW - Online Target Date Assignment Problem Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8945 ER - TY - CHAP A1 - Heinz, Stefan A1 - Krumke, Sven A1 - Megow, Nicole A1 - Rambau, Jörg A1 - Tuchscherer, Andreas A1 - Vredeveld, Tjark ED - Erlebach, Thomas ED - Persiano, Giuseppe T1 - The Online Target Date Assignment Problem T2 - Proc. 3rd Workshop on Approximation and Online Algorithms Y1 - 2006 UR - http://opus.kobv.de/zib/volltexte/2005/894/ VL - 3879 SP - 230 EP - 243 PB - Springer ER - 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 - Athanasiadis, Christos A. A1 - Rambau, Jörg A1 - Santos, Francisco T1 - The Generalized Baues Problem for Cyclic Polytopes II N2 - Given an affine surjection of polytopes $\pi: P \to Q$, the Generalized Baues Problem asks whether the poset of all proper polyhedral subdivisions of $Q$ which are induced by the map $\pi$ has the homotopy type of a sphere. We extend earlier work of the last two authors on subdivisions of cyclic polytopes to give an affirmative answer to the problem for the natural surjections between cyclic polytopes $\pi: C(n,d') \to C(n,d)$ for all $1 \leq d < d' < n$. T3 - ZIB-Report - SC-98-43 KW - Generalized Baues Problem KW - Polyhedral Subdivisions KW - Induced Subdivisions KW - Poset KW - Spherical KW - Cyclic Polytopes KW - Bistellar Operations Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3862 ER -