@misc{KrumkeRambau, author = {Krumke, Sven and Rambau, J{\"o}rg}, title = {Probieren geht {\"u}ber Studieren? Entscheidungshilfen f{\"u}r kombinatorische Online-Optimierungsprobleme in der innerbetrieblichen Logistik}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6723}, number = {02-05}, abstract = {Die Automatisierung von innerbetrieblicher Logistik erfordert -- {\"u}ber die physikalische Steuerung von Ger{\"a}ten hinaus -- auch eine effiziente Organisation der Transporte: ein Aufgabenfeld der kombinatorischen Optimierung. Dieser Artikel illustriert anhand von konkreten Aufgabenstellungen die Online-Problematik (unvollst{\"a}ndiges Wissen) sowie die Echtzeit-Problematik (beschr{\"a}nkte Rechenzeit), auf die man in der innerbetrieblichen Logistik trifft. Der Text gibt einen {\"U}berblick {\"u}ber allgemeine Konstruktionsprinzipien f{\"u}r Online-Algorithmen und Bewertungsmethoden, die bei der Entscheidung helfen, welche Algorithmen f{\"u}r eine vorliegende Problemstellung geeignet sind.}, language = {de} } @misc{KrumkePaepeRambauetal., author = {Krumke, Sven and Paepe, Willem de and Rambau, J{\"o}rg and Stougie, Leen}, title = {Online Bin-Coloring}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6338}, number = {01-07}, abstract = {We introduce a new problem that was motivated by a (more complicated) problem arising in a robotized assembly enviroment. The bin coloring problem is to pack unit size colored items into bins, such that the maximum number of different colors per bin is minimized. Each bin has size~\$B\in\mathbb{N}\$. The packing process is subject to the constraint that at any moment in time at most \$q\in\mathbb{N}\$ bins may be partially filled. Moreover, bins may only be closed if they are filled completely. An online algorithm must pack each item must be packed without knowledge of any future items. We investigate the existence of competitive online algorithms for the online uniform binpacking problem. We show upper bounds for the bin coloring problem. We prove an upper bound of \$3q\$ - 1 and a lower bound of \$2q\$ for the competitive ratio of a natural greedy-type algorithm, and show that surprisingly a trivial algorithm which uses only one open bin has a strictly better competitive ratio of \$2q\$ - 1. Morever, we show that any deterministic algorithm has a competitive ratio \$\Omega (q)\$ and that randomization does not improve this lower bound even when the adversary is oblivious.}, language = {en} } @misc{KrumkeLipmannPaepeetal., author = {Krumke, Sven and Lipmann, Maarten and Paepe, Willem de and Poensgen, Diana and Rambau, J{\"o}rg and Stougie, Leen and Woeginger, Gerhard}, title = {How to Cut a Cake Almost Fairly}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6905}, number = {02-23}, abstract = {In the cake cutting problem, \$n\ge2\$ players want to cut a cake into \$n\$ pieces so that every player gets a ``fair'' share of the cake by his own measure. We describe a protocol with \$n-1\$~cuts in which each player can enforce to get a share of at least~\$1/(2n-2)\$. Moreover we show that no protocol with \$n-1\$~cuts can guarantee a better fraction.}, language = {en} } @inproceedings{HuelsermannJaegerPoensgenetal.2003, author = {H{\"u}lsermann, Ralf and J{\"a}ger, Monika and Poensgen, Diana and Krumke, Sven and Rambau, J{\"o}rg and Tuchscherer, Andreas}, title = {Dynamic routing algorithms in transparent optical networks}, series = {Proceedings of the 7th IFIP Working Conference on Optical Network Design \& Modelling (ONDM 2003)}, booktitle = {Proceedings of the 7th IFIP Working Conference on Optical Network Design \& Modelling (ONDM 2003)}, editor = {Cinkler, Tibor and Jakab, Tivadar and Tapolcai, J{\`a}nos and G{\`a}sp{\`a}r, Csaba}, publisher = {Kluwer Academic Press}, pages = {293 -- 312}, year = {2003}, language = {en} } @misc{HuelsermannJaegerKrumkeetal., author = {H{\"u}lsermann, Ralf and J{\"a}ger, Monika and Krumke, Sven and Poensgen, Diana and Rambau, J{\"o}rg and Tuchscherer, Andreas}, title = {Dynamic Routing Algorithms in Transparent Optical Networks An Experimental Study Based on Real Data}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7025}, number = {02-35}, abstract = {Today's telecommunication networks are configured statically. Whenever a connection is established, the customer has permanent access to it. However, it is observed that usually the connection is not used continuously. At this point, dynamic provisioning could increase the utilization of network resources. WDM based Optical Transport Networks (OTNs) will shortly allow for fast dynamic network reconfiguration. This enables optical broadband leased line services on demand. Since service requests competing for network resources may lead to service blocking, it is vital to use appropriate strategies for routing and wavelength assignment in transparent optical networks. We simulate the service blocking probabilities of various dynamic algorithms for this problem using a well-founded traffic model for two realistic networks. One of the algorithms using shortest path routings performs best on all instances. Surprisingly, the tie-breaking rule between equally short paths in different wavelengths decides between success or failure.}, language = {en} } @misc{HuberRambauSantos, author = {Huber, Birkett and Rambau, J{\"o}rg and Santos, Francisco}, title = {The Cayley Trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3874}, number = {SC-98-44}, abstract = {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.}, language = {en} } @misc{HillerKrumkeRambau, author = {Hiller, Benjamin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Reoptimization Gaps versus Model Errors in Online-Dispatching of Service Units for ADAC}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7928}, number = {04-17}, abstract = {Under high load, the automated dispatching of service vehicles for the German Automobile Association (ADAC) must reoptimize a dispatch for 100--150 vehicles and 400 requests in about ten seconds to near optimality. In the presence of service contractors, this can be achieved by the column generation algorithm ZIBDIP. In metropolitan areas, however, service contractors cannot be dispatched automatically because they may decline. The problem: a model without contractors yields larger optimality gaps within ten seconds. One way-out are simplified reoptimization models. These compute a short-term dispatch containing only some of the requests: unknown future requests will influence future service anyway. The simpler the models the better the gaps, but also the larger the model error. What is more significant: reoptimization gap or reoptimization model error? We answer this question in simulations on real-world ADAC data: only the new model ZIBDIP{\footnotesize dummy} can keep up with ZIBDIP.}, language = {en} } @article{HillerKrumkeRambau2006, author = {Hiller, Benjamin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Reoptimization Gaps versus Model Errors in Online-Dispatching of Service Units for ADAC}, series = {DISAM}, volume = {154}, journal = {DISAM}, number = {13}, pages = {1897 -- 1907}, year = {2006}, language = {en} } @inproceedings{HillerKrumkeRambau2004, author = {Hiller, Benjamin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Reoptimization Gaps versus Model Errors in Online-Dispatching of Service Units for ADAC}, series = {Latin-American Conference on Combinatorics, Graphs and Applications, Santiago de Chile 2004}, volume = {18}, booktitle = {Latin-American Conference on Combinatorics, Graphs and Applications, Santiago de Chile 2004}, editor = {Liebling, T. and Duran, G. and Matamala, M.}, pages = {157 -- 163}, year = {2004}, language = {en} } @misc{HeinzKrumkeMegowetal., author = {Heinz, Stefan and Krumke, Sven and Megow, Nicole and Rambau, J{\"o}rg and Tuchscherer, Andreas and Vredeveld, Tjark}, title = {The Online Target Date Assignment Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8945}, number = {05-61}, abstract = {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.}, language = {en} }