@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{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} } @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} } @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} }