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 - TY - GEN A1 - Huber, Birkett A1 - Rambau, Jörg A1 - Santos, Francisco T1 - The Cayley Trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings N2 - In 1994, Sturmfels gave a polyhedral version of the Cayley Trick of elimination theory: he established an order-preserving bijection between the posets of \emph{coherent} mixed subdivisions of a Minkowski sum $\mathcal{A}_1+\cdots+\mathcal{A}_r$ of point configurations and of \emph{coherent} polyhedral subdivisions of the associated Cayley embedding $\mathcal{C}(\mathcal{A}_1,\dots,\mathcal{A}_r)$. In this paper we extend this correspondence in a natural way to cover also \emph{non-coherent} subdivisions. As an application, we show that the Cayley Trick combined with results of Santos on subdivisions of Lawrence polytopes provides a new independent proof of the Bohne-Dress Theorem on zonotopal tilings. This application uses a combinatorial characterization of lifting subdivisions, also originally proved by Santos. T3 - ZIB-Report - SC-98-44 KW - Polyhedral subdivision KW - fiber polytope KW - mixed subdivision KW - lifting subdivision KW - Minkowski sum KW - Cayley Trick KW - Bohne-Dress Theorem Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3874 ER - 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 - GEN A1 - Hauptmeier, Dietrich A1 - Krumke, Sven A1 - Rambau, Jörg A1 - Wirth., Hans-Christoph T1 - Euler is Standing in Line N2 - In this paper we study algorithms for ``Dial-a-Ride'' transportation problems. In the basic version of the problem we are given transportation jobs between the vertices of a graph and the goal is to find a shortest transportation that serves all the jobs. This problem is known to be NP-hard even on trees. We consider the extension when precedence relations between the jobs with the same source are given. Our results include a polynomial time algorithm on paths and an approximation algorithm on general graphs with a performance of~$9/4$. For trees we improve the performance to~$5/3$. T3 - ZIB-Report - SC-99-06 KW - NP-completeness KW - polynomial-time approximation algorithms KW - stacker-crane problem KW - vehicle routing KW - elevator system KW - Eulerian Cycle Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3947 ER - TY - CHAP A1 - Ascheuer, Norbert A1 - Grötschel, Martin A1 - Krumke, Sven A1 - Rambau, Jörg ED - Kall, Peter ED - Lüthi, Hans-Jakob T1 - Combinatorial Online Optimization T2 - Operations Research Proceedings 1998. Selected Papers of the International Conference on Operations Research Zurich, August 31 – September 3, 1998 Y1 - 1999 SP - 21 EP - 37 PB - Springer 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 - 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 - Hauptmeier, Dietrich A1 - Krumke, Sven A1 - Rambau, Jörg T1 - Simulation Studies for the Online-Dial-a-Ride Problem N2 - In a large distribution center of Herlitz AG, Berlin, we invesigated the elevator subsystem of the fully automated pallet transportation system. Each elevator may carry one pallet and has to serve eight levels. The goal is to minimize the average resp.\ the maximum flow time. The variants of this elevator control problem have been subject of recent theoretical research and are known as online-dial-a-ride problems. In this paper we investigate several online algorithms for several versions of online-dial-a-ride problems by means of a simulation program, developed on the basis of the simulation library AMSEL. We draw statistics from samples of randomly generated data providing for different load situations. Moreover, we provide preliminary studies with real production data for a system of five elevators connected by a conveyor circuit, as can be found at the Herlitz plant. We show which algorithms are best under certain load situations and which lead to break downs under particular circumstances. T3 - ZIB-Report - SC-99-09 KW - online optimization KW - competitive analysis KW - elevator KW - simulation studies Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3976 ER -