@misc{KonjevodKrumkeMarathe, author = {Konjevod, Goran and Krumke, Sven and Marathe, Madhav}, title = {Budget Constrained Minimum Cost Connected Medians}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5783}, number = {00-10}, abstract = {Several practical instances of network design problems require the network to satisfy multiple constraints. In this paper, we address the \emph{Budget Constrained Connected Median Problem}: We are given an undirected graph \$G = (V,E)\$ with two different edge-weight functions \$c\$ (modeling the construction or communication cost) and \$d\$ (modeling the service distance), and a bound~\$B\$ on the total service distance. The goal is to find a subtree~\$T\$ of \$G\$ with minimum \$c\$-cost \$c(T)\$ subject to the constraint that the sum of the service distances of all the remaining nodes \$v \in V\setminus T\$ to their closest neighbor in~\$T\$ does not exceed the specified budget~\$B\$. This problem has applications in optical network design and the efficient maintenance of distributed databases. We formulate this problem as bicriteria network design problem, and present bicriteria approximation algorithms. We also prove lower bounds on the approximability of the problem that demonstrate that our performance ratios are close to best possible}, 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{KrumkeLauraLipmannetal., author = {Krumke, Sven and Laura, Luigi and Lipmann, Maarten and Marchetti-Spaccamela, Alberto and Paepe, Willem de and Poensgen, Diana and Stougie, Leen}, title = {Non-Abusiveness Helps: An O(1)-Competitive Algorithm for Minimizing the Maximum Flow Time in the Online Traveling Salesman Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7038}, number = {02-36}, abstract = {In the online traveling salesman problem \$OLTSP\$ requests for visits to cities arrive online while the salesman is traveling. We study the \$F{\_max}-OLTSP\$ where the objective is to minimize the maximum flow time. This objective is particularly interesting for applications. Unfortunately, there can be no competitive algorithm, neither deterministic nor randomized. Hence, competitive analysis fails to distinguish online algorithms. Not even resource augmentation which is helpful in scheduling works as a remedy. This unsatisfactory situation motivates the search for alternative analysis methods. We introduce a natural restriction on the adversary for the \$F{\_max}-OLTSP\$ on the real line. A \emph{non-abusive adversary} may only move in a direction if there are yet unserved requests on this side. Our main result is an algorithm which achieves a constant competitive ratio against the non-abusive adversary.}, language = {en} } @misc{GroetschelKrumkeRambauetal., author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg and Torres, Luis Miguel}, title = {Making the Yellow Angels Fly: Online Dispatching Of Service Vehicles in Real Time}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6858}, number = {02-18}, abstract = {Combinatorial online optimization is an area with lots of applications and potential for significant progress, both in theory and practice. In this short note we sketch the ADACproblem, a typical large-scale online optimization problem, discuss some theoretical and pratical issues coming up, and explain, very briefly, how we approach this problem mathematically. Online problems are a battlefield of heuristics with many strong claims about their solution quality. We indicate that a stronger problem orientation and the use of a little more mathematics may yield.}, language = {en} } @misc{KrumkePoensgen, author = {Krumke, Sven and Poensgen, Diana}, title = {Online Call Admission in Optical Networks with Larger Wavelength Demands}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6890}, number = {02-22}, abstract = {In the problem of \emph{Online Call Admission in Optical Networks}, briefly called \textsc{oca}, we are given a graph \$G=(V,E)\$ together with a set of wavelengths~\$W\$ and a finite sequence \$\sigma=r_1,r_2,\dots\$ of calls which arrive in an online fashion. Each call~\$r_j\$ specifies a pair of nodes to be connected and an integral demand indicating the number of required lightpaths. A lightpath is a path in~\$G\$ together with a wavelength~\$\lambda \in W\$. Upon arrival of a call, an online algorithm must decide immediately and irrevocably whether to accept or to reject the call without any knowledge of calls which appear later in the sequence. If the call is accepted, the algorithm must provide the requested number of lightpaths to connect the specified nodes. The essential restriction is the wavelength conflict constraint: each wavelength is available only once per edge, which implies that two lightpaths sharing an edge must have different wavelengths. Each accepted call contributes a benefit equal to its demand to the overall profit. The objective in \textsc{oca} is to maximize the overall profit. Competitive algorithms for \textsc{oca} have been known for the special case where every call requests just a single lightpath. In this paper we present the first competitive online algorithms for the general case of larger demands.}, 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} } @misc{KrumkeMarathePoensgenetal., author = {Krumke, Sven and Marathe, Madhav and Poensgen, Diana and Ravi, Sekharipuram S. and Wirth, Hans-Christoph}, title = {Budgeted Maximal Graph Coverage}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6918}, number = {02-24}, abstract = {An instance of the \emph{maximum coverage} problem is given by a set of weighted ground elements and a cost weighted family of subsets of the ground element set. The goal is to select a subfamily of total cost of at most that of a given budget maximizing the weight of the covered elements. We formulate the problem on graphs: In this situation the set of ground elements is specified by the nodes of a graph, while the family of covering sets is restricted to connected subgraphs. We show that on general graphs the problem is polynomial time solvable if restricted to sets of size at most~\$2\$, but becomes NP-hard if sets of size~\$3\$ are permitted. On trees, we prove polynomial time solvability if each node appears in a fixed number of sets. In contrast, if vertices are allowed to appear an unbounded number of times, the problem is NP-hard even on stars. We finally give polynomial time algorithms for special cases where the subgraphs form paths and the host graph is a line, a cycle or a star.}, language = {en} } @phdthesis{Krumke, author = {Krumke, Sven}, title = {Online Optimization: Competitive Analysis and Beyond}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6925}, number = {02-25}, abstract = {Traditional optimization techniques assume, in general, knowledge of all data of a problem instance. There are many cases in practice, however, where decisions have to be made before complete information about the data is available. In fact, it may be necessary to produce a part of the problem solution as soon as a new piece of information becomes known. This is called an \emph{online situation}, and an algorithm is termed \emph{online}, if it makes a decision (computes a partial solution) whenever a new piece of data requests an action. \emph{Competitive analysis} has become a standard yardstick to measure the quality of online algorithms. One compares the solution produced by an online algorithm to that of an optimal (clairvoyant) offline algorithm. An online algorithm is called \$c\$-competitive if on every input the solution it produces has cost'' at most \$c\$~times that of the optimal offline algorithm. This situation can be imagined as a game between an online player and a malicious adversary. Although competitive analysis is a worst-case analysis and henceforth pessimistic, it often allows important insights into the problem structure. One can obtain an idea about what kind of strategies are promising for real-world systems and why. On the other hand there are also cases where the offline adversary is simply too powerful and allows only trivial competitiveness results. This phenomenon is called hitting the triviality barrier''. We investigate several online problems by means of competitive analysis. We also introduce new concepts to overcome the weaknesses of the standard approach and to go beyond the triviality barrier.}, language = {en} } @misc{GroetschelKrumkeRambauetal., author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg and Winter, Thomas and Zimmermann, Uwe}, title = {Combinatorial Online Optimization in Real Time}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6424}, number = {01-16}, abstract = {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.}, language = {en} } @misc{GroetschelKrumkeRambau, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Online Optimization of Complex Transportation Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6438}, number = {01-17}, abstract = {This paper discusses online optimization of real-world transportation systems. We concentrate on transportation problems arising in production and manufacturing processes, in particular in company internal logistics. We describe basic techniques to design online optimization algorithms for such systems, but our main focus is decision support for the planner: which online algorithm is the most appropriate one in a particular setting? We show by means of several examples that traditional methods for the evaluation of online algorithms often do not suffice to judge the strengths and weaknesses of online algorithms. We present modifications of well-known evaluation techniques and some new methods, and we argue that the selection of an online algorithm to be employed in practice should be based on a sound combination of several theoretical and practical evaluation criteria, including simulation.}, language = {en} } @misc{KrumkeRambauTorres, author = {Krumke, Sven and Rambau, J{\"o}rg and Torres, Luis Miguel}, title = {Real-Time Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6484}, number = {01-22}, abstract = {Given a set of service requests (events), a set of guided servers (units), and a set of unguided service contractors (conts), the vehicle dispatching problem {\sl vdp} is the task to find an assignment of events to units and conts as well as tours for all units starting at their current positions and ending at their home positions (dispatch) such that the total cost of the dispatch is minimized. The cost of a dispatch is the sum of unit costs, cont costs, and event costs. Unit costs consist of driving costs, service costs and overtime costs; cont costs consist of a fixed cost per service; event costs consist of late costs linear in the late time, which occur whenever the service of the event starts later than its deadline. The program \textsf{ZIBDIP} based on dynamic column generation and set partitioning yields solutions on heavy-load real-world instances (215 events, 95 units) in less than a minute that are no worse than 1\\% from optimum on state-of-the-art personal computers.}, language = {en} } @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{KrumkeRambauTorres, author = {Krumke, Sven and Rambau, J{\"o}rg and Torres, Luis Miguel}, title = {Online-Dispatching of Automobile Service Units}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7117}, number = {02-44}, abstract = {We present an online algorithm for a real-world vehicle dispatching problem at ADAC, the German Automobile Association.}, 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} } @misc{HillerKrumkeSalibaetal., author = {Hiller, Benjamin and Krumke, Sven and Saliba, Sleman and Tuchscherer, Andreas}, title = {Randomized Online Algorithms for Dynamic Multi-Period Routing Problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11132}, number = {09-03}, abstract = {The Dynamic Multi-Period Routing Problem DMPRP introduced by Angelelli et al. gives a model for a two-stage online-offline routing problem. At the beginning of each time period a set of customers becomes known. The customers need to be served either in the current time period or in the following. Postponed customers have to be served in the next time period. The decision whether to postpone a customer has to be done online. At the end of each time period, an optimal tour for the customers assigned to this period has to be computed and this computation can be done offline. The objective of the problem is to minimize the distance traveled over all planning periods assuming optimal routes for the customers selected in each period. We provide the first randomized online algorithms for the DMPRP which beat the known lower bounds for deterministic algorithms. For the special case of two planning periods we provide lower bounds on the competitive ratio of any randomized online algorithm against the oblivious adversary. We identify a randomized algorithm that achieves the optimal competitive ratio of \$\frac{1+\sqrt{2}}{2}\$ for two time periods on the real line. For three time periods, we give a randomized algorithm that is strictly better than any deterministic algorithm.}, 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} } @misc{GroetschelKrumkeRambau, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Wo bleibt der Aufzug?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4175}, number = {SC-99-29}, abstract = {Dieser Artikel gibt eine allgemeinverst{\"a}ndliche Einf{\"u}hrung in die spezielle Problematik kombinatorischer Online-Problem am Beispiel der Fahrstuhlsteuerung.}, language = {de} } @misc{HauptmeierKrumkeRambauetal., author = {Hauptmeier, Dietrich and Krumke, Sven and Rambau, J{\"o}rg and Wirth., Hans-Christoph}, title = {Euler is Standing in Line}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3947}, number = {SC-99-06}, abstract = {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\$.}, language = {en} } @misc{AscheuerGroetschelKrumkeetal., author = {Ascheuer, Norbert and Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Combinatorial Online Optimization}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3674}, number = {SC-98-24}, abstract = {In ``classical'' optimization, all data of a problem instance are considered given. The standard theory and the usual algorithmic techniques apply to such cases only. Online optimization is different. Many decisions have to be made before all data are available. In addition, decisions once made cannot be changed. How should one act ``best'' in such an environment? In this paper we survey online problems coming up in combinatorial optimization. We first outline theoretical concepts, such as competitiveness against various adversaries, to analyze online problems and algorithms. The focus, however, lies on real-world applications. We report, in particular, on theoretical investigations and our practical experience with problems arising in transportation and the automatic handling of material.}, language = {en} } @misc{KrumkeNoltemeierWirth, author = {Krumke, Sven and Noltemeier, Hartmut and Wirth, Hans-Christoph}, title = {Graphentheoretische Konzepte und Algorithmen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5873}, number = {00-19}, abstract = {Das vorliegende Skript bietet eine Einf{{\"u}}hrung in die Graphentheorie und graphentheoretische Algorithmen. Im zweiten Kapitel werden Grundbegriffe der Graphentheorie vorgestellt. Das dritte Kapitel besch{{\"a}}ftigt sich mit der Existenz von Wegen in Graphen. Hier wird auch die L{{\"o}}suung des ber{{\"u}}hmten K{{\"o}}nigsberger Br{{\"u}}ckenproblems aufgezeigt und der Satz von Euler bewiesen. Im vierten Kapitel wird gezeigt, wie man auf einfache Weise die Zusammenhangskomponenten eines Graphen bestimmen kann. Im Kapitel sechs wird dann sp{{\"a}}ter mit der Tiefensuche ein Verfahren vorgestellt, das schneller arbeitet und mit dessen Hilfe man noch mehr Informationen {{\"u}}ber die Struktur eines Graphen gewinnen kann. In den folgenden Kapiteln werden Algorithmen vorgestellt, um minimale aufspannenden B{{\"a}}ume, k{{\"u}}rzeste Wege und maximale Fl{{\"u}}sse in Graphen zu bestimmen. Am Ende des Skripts wird ein kurzer Einblick in die planaren Graphen und Graphhomomorphismen geboten.}, language = {de} } @misc{KrumkeRambauWeider, author = {Krumke, Sven and Rambau, J{\"o}rg and Weider, Steffen}, title = {An Approximation Algorithm for the Non-Preemptive Capacitated Dial-a-Ride Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6217}, number = {00-53}, abstract = {In the Capacitated Dial-a-Ride Problem (CDARP) we are given a transportation network and a finite set of transportation jobs. Each job specifies the source and target location which are both part of the network. A server which can carry at most \$C\$~objects at a time can move on the transportation network in order to process the transportation requests. The problem CDARP consists of finding a shortest transportation for the jobs starting and ending at a designated start location. In this paper we are concerned with the restriction of CDARP to graphs which are simple paths. This setting arises for instance when modelling applications in elevator transportation systems. It is known that even for this restricted class of graphs CDARP is NP-hard to solve. We provide a polynomial time approximation algorithm that finds a transportion of length at most thrice the length of the optimal transportation.}, language = {en} } @misc{KrumkeRambau, author = {Krumke, Sven and Rambau, J{\"o}rg}, title = {Online Optimierung}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6238}, number = {00-55}, abstract = {Wie soll man einen Aufzug steuern, wenn man keine Informationen {\"u}ber zuk{\"u}nftige Fahrauftr{\"a}ge besitzt? Soll man eine Bahncard kaufen, wenn die n{\"a}chsten Bahnreisen noch unbekannt sind? In der klassischen kombinatorischen Optimierung geht man davon aus, daß die Daten jeder Probleminstanz vollst{\"a}ndig gegeben sind. In vielen F{\"a}llen modelliert diese \emph{Offline-Optimierung} jedoch die Situationen aus Anwendungen nur ungen{\"u}gend. Zahlreiche Problemstellungen in der Praxis sind in nat{\"u}rlicher Weise \emph{online}: Sie erfordern Entscheidungen, die unmittelbar und ohne Wissen zuk{\"u}nftiger Ereignisse getroffen werden m{\"u}ssen. Als ein Standardmittel zur Beurteilung von Online-Algorithmen hat sich die \emph{kompetitive Analyse} durchgesetzt. Dabei vergleicht man den Zielfunktionswert einer vom Online-Algorithmus generierten L{\"o}sung mit dem Wert einer optimalen Offline-L{\"o}sung. Mit Hilfe der kompetitiven Analyse werden im Skript Algorithmen zum Caching, Netzwerk-Routing, Scheduling und zu Transportaufgaben untersucht. Auch die Schw{\"a}chen der kompetitiven Analyse werden aufgezeigt und alternative Analysekonzepte vorgestellt. Neben der theoretischen Seite werden auch die Anwendungen der Online-Optimierung in der Praxis, vor allem bei Problemen der innerbetrieblichen Logistik, beleuchtet. Bei der Steuerung automatischer Transportsysteme tritt eine F{\"u}lle von Online-Problemen auf. Hierbei werden an die Algorithmen oftmals weitere Anforderungen gestellt. So m{\"u}ssen Entscheidungen unter strikten Zeitbeschr{\"a}nkungen gef{\"a}llt werden (Echtzeit-Anforderungen). Dieses Skript ist aus dem Online-Teil der Vorlesung -Ausgew{\"a}hlte Kapitel aus der ganzzahligen Optimierung- (Wintersemester~1999/2000) und der Vorlesung -Online Optimierung- (Sommersemester~2000) an der Technischen Universit{\"a}t Berlin entstanden.}, language = {de} } @inproceedings{AscheuerGroetschelKrumkeetal.1999, author = {Ascheuer, Norbert and Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Combinatorial Online Optimization}, series = {Operations Research Proceedings 1998. Selected Papers of the International Conference on Operations Research Zurich, August 31 - September 3, 1998}, booktitle = {Operations Research Proceedings 1998. Selected Papers of the International Conference on Operations Research Zurich, August 31 - September 3, 1998}, editor = {Kall, Peter and L{\"u}thi, Hans-Jakob}, publisher = {Springer}, pages = {21 -- 37}, year = {1999}, language = {en} } @article{GroetschelKrumkeRambau1999, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Wo bleibt der Aufzug?}, series = {OR News}, volume = {5}, journal = {OR News}, pages = {11 -- 13}, year = {1999}, language = {en} } @article{GroetschelKrumkeRambau2006, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Wo bleibt der Aufzug?}, series = {OR News}, volume = {Sonderausgabe}, journal = {OR News}, pages = {70 -- 72}, year = {2006}, language = {en} } @article{GroetschelKrumkeRambauetal.2002, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg and Torres, Luis Miguel}, title = {Making the Yellow Angels Fly}, series = {SIAM News}, volume = {35}, journal = {SIAM News}, number = {4}, pages = {1,10,11}, year = {2002}, language = {en} } @incollection{GroetschelKrumkeRambau2001, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, title = {Online Optimization of Complex Transportation Systems}, series = {Online Optimization of Large Scale Systems}, booktitle = {Online Optimization of Large Scale Systems}, editor = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, publisher = {Springer}, pages = {705 -- 729}, year = {2001}, language = {en} } @incollection{GroetschelKrumkeRambauetal.2001, author = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg and Winter, Thomas and Zimmermann, Uwe}, title = {Combinatorial Online Optimization in Real Time}, series = {Online Optimization of Large Scale Systems}, booktitle = {Online Optimization of Large Scale Systems}, editor = {Gr{\"o}tschel, Martin and Krumke, Sven and Rambau, J{\"o}rg}, publisher = {Springer}, pages = {679 -- 704}, year = {2001}, language = {en} } @inproceedings{HillerKrumkeSalibaetal.2009, author = {Hiller, Benjamin and Krumke, Sven and Saliba, Sleman and Tuchscherer, Andreas}, title = {Randomized Online Algorithms for Dynamic Multi-Period Routing Problems}, series = {Proceedings of MAPSP}, booktitle = {Proceedings of MAPSP}, pages = {71 -- 73}, year = {2009}, 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} } @inproceedings{HeinzKrumkeMegowetal.2006, 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}, series = {Proc. 3rd Workshop on Approximation and Online Algorithms}, volume = {3879}, booktitle = {Proc. 3rd Workshop on Approximation and Online Algorithms}, editor = {Erlebach, Thomas and Persiano, Giuseppe}, publisher = {Springer}, pages = {230 -- 243}, year = {2006}, 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{AscheuerKrumkeRambau, author = {Ascheuer, Norbert and Krumke, Sven and Rambau, J{\"o}rg}, title = {The Online Transportation Problem: Competitive Scheduling of Elevators}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3779}, number = {SC-98-34}, abstract = {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.}, language = {en} } @misc{BlomKrumkePaepeetal., author = {Blom, Michiel and Krumke, Sven and Paepe, Willem de and Stougie, Leen}, title = {The Online-TSP Against Fair Adversaries}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5779}, number = {00-09}, abstract = {In the online traveling salesman problem requests for visits to cities (points in a metric space) arrive online while the salesman is traveling. The salesman moves at no more than unit speed and starts and ends his work at a designated origin. The objective is to find a routing for the salesman which finishes as early as possible. Performance of algorithms is measured through their competitive ratio, comparing the outcome of the algorithms with that of an adversary who provides the problem instance and therefore is able to achieve the optimal offline solution. Objections against such omnipotent adversaries have lead us to devise an adversary that is in a natural way, in the context of routing problems, more restricted in power. For the exposition we consider the online traveling salesman problem on the metric space given by the non-negative part of the real line. We show that a very natural strategy is~\$3/2\$-competitive against the conventional adversary, which matches the lower bound on competitive ratios achievable for algorithms for this problem. Against the more ``\emph{fair adversary}'', that we propose, we show that there exists an algorithm with competitive ratio \$\frac{1+\sqrt{17}}{4}\approx 1.28\$ and provide a matching lower bound. We also show competitiveness results for a special class of algorithms (called zealous algorithms) that do not allow waiting time for the server as long as there are requests unserved.}, language = {en} } @misc{CojaOghlanKrumkeNierhoff, author = {Coja-Oghlan, Amin and Krumke, Sven and Nierhoff, Till}, title = {Average Case Analysis of a Hard Dial-a-Ride Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7348}, number = {03-12}, abstract = {In the dial-a-ride-problem (DARP) objects have to be moved between given sources and destinations in a transportation network by means of a server. The goal is to find a shortest transportation for the server. We study the DARP when the underlying transportation network forms a caterpillar. This special case is strongly NP-hard in the worst case. We prove that in a probabilistic setting there exists a polynomial time algorithm which almost surely finds an optimal solution. Moreover, with high probability the optimality of the solution found can be certified efficiently. We also examine the complexity of the DARP in a semi-random setting and in the unweighted case.}, language = {en} } @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{Krumke, author = {Krumke, Sven}, title = {News from the Online Traveling Repairman}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5767}, number = {00-08}, abstract = {The traveling repairman problem (TRP) is a variant of the famous traveling salesman problem (TSP). The objective for the TRP is to minimize the latency, that is the the weighted sum of completion times of the cities, where the completion time of a city is defined to be the time in the tour before the city is reached. In the online traveling repairman problem (OLTRP) requests for visits to cities (points in a metric space) arrive online while the repairman is traveling. We analyze the performance of algorithms using competitive analysis, where the cost of an online algorithm is compared to that of an optimal offline algorithm. An optimal offline algorithm knows the entire request sequence in advance and can serve it with minimum cost. Recently, Feuerstein and Stougie presented a \$9\$-competitive algorithm for the OLTRP on the real line. In this paper we show how to use techniques from online-scheduling to obtain an \$8\$-competitive deterministic algorithm which works for any metric space. We also present a randomized algorithm which has a competitive ratio of \$\frac{4}{\ln 2}\approx 5.7708\$ against an oblivious adversary. All of our results also hold for the ``dial-a-ride'' generalization of the OLTRP, where objects have to be picked up and delivered by a server.}, language = {en} } @misc{HauptmeierKrumkeRambau, author = {Hauptmeier, Dietrich and Krumke, Sven and Rambau, J{\"o}rg}, title = {The Online Dial-a-Ride Problem under Reasonable Load}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3961}, number = {SC-99-08}, abstract = {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.}, language = {en} } @misc{GroetschelHauptmeierKrumkeetal., author = {Gr{\"o}tschel, Martin and Hauptmeier, Dietrich and Krumke, Sven and Rambau, J{\"o}rg}, title = {Simulation Studies for the Online-Dial-a-Ride Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3976}, number = {SC-99-09}, abstract = {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.}, language = {en} }