TY - GEN A1 - Hiller, Benjamin T1 - Probabilistic Competitive Analysis of a Dial-a-Ride Problem on Trees Under High Load N2 - In this paper we consider a simple variant of the Online Dial-a-Ride Problem from a probabilistic point of view. To this end, we look at a probabilistic version of this online Dial-a-Ride problem and introduce a probabilistic notion of the competitive ratio which states that an algorithm performs well on the vast majority of the instances. Our main result is that under the assumption of high load a certain online algorithm is probabilistically $(1+o(1))$-competitive if the underlying graph is a tree. This result can be extended to general graphs by using well-known approximation techniques at the expense of a distortion factor~$O(\log\|V\|)$. T3 - ZIB-Report - 05-56 KW - probabilistic competitive analysis KW - Dial-a-Ride problem KW - online algorithms KW - IGNORE strategy Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8896 ER - TY - GEN A1 - Krumke, Sven A1 - Laura, Luigi A1 - Lipmann, Maarten A1 - Marchetti-Spaccamela, Alberto A1 - Paepe, Willem de A1 - Poensgen, Diana A1 - Stougie, Leen T1 - Non-Abusiveness Helps: An O(1)-Competitive Algorithm for Minimizing the Maximum Flow Time in the Online Traveling Salesman Problem N2 - 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. T3 - ZIB-Report - 02-36 KW - Online Algorithms KW - Competitive Analysis KW - Comparative Analysis Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7038 ER - TY - GEN A1 - Krumke, Sven A1 - Poensgen, Diana T1 - Online Call Admission in Optical Networks with Larger Wavelength Demands N2 - 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. T3 - ZIB-Report - 02-22 KW - Call Admission KW - Routing and Wavelength Allocation KW - Optical Networks KW - Competitive Analysis KW - Colorability Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6890 ER - TY - GEN A1 - Krumke, Sven T1 - News from the Online Traveling Repairman N2 - 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. T3 - ZIB-Report - 00-08 KW - Traveling Repairman KW - Latency KW - Dial-a-Ride-Problem KW - Competitive Analysis Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5767 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 - GEN A1 - Krumke, Sven A1 - Paepe, Willem de A1 - Rambau, Jörg A1 - Stougie, Leen T1 - Online Bin-Coloring N2 - 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. T3 - ZIB-Report - 01-07 KW - Online Optimization KW - randomized algorithms KW - lower bounds KW - competitive analysis Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6338 ER - TY - GEN A1 - Hiller, Benjamin A1 - Vredeveld, Tjark T1 - Probabilistic analysis of Online Bin Coloring algorithms via Stochastic Comparison N2 - This paper proposes a new method for probabilistic analysis of online algorithms that is based on the notion of stochastic dominance. We develop the method for the Online Bin Coloring problem introduced by Krumke et al. Using methods for the stochastic comparison of Markov chains we establish the strong result that the performance of the online algorithm GreedyFit is stochastically dominated by the performance of the algorithm OneBin for any number of items processed. This result gives a more realistic picture than competitive analysis and explains the behavior observed in simulations. T3 - ZIB-Report - 08-18 KW - Stochastische Dominanz KW - Online-Algorithmen KW - Markov-Ketten KW - Probabilistische Analyse KW - stochastic dominance KW - online algorithms KW - Markov chains KW - probabilistic analysis Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10726 SN - 1438-0064 ER - TY - THES A1 - Hiller, Benjamin T1 - Bad Guys are Rare: Probabilistic Analysis of an Elementary Dial-a-Ride Problem N2 - This thesis deals with a Dial-a-Ride problem on trees and considers both offline and online versions of this problem. We study the behavior of certain algorithms on random instances, i.e. we do probabilistic analysis. The focus is on results describing the typical behavior of the algorithms, i.e. results holding with (asymptotically) high probability. For the offline version, we present a simplified proof of a result of Coja-Oghlan, Krumke und Nierhoff. The results states that some heuristic using a minimum spanning tree to approximate a Steiner tree gives optimal results with high probability. This explains why this heuristic produces optimal solutions quite often. In the second part, probabilistic online versions of the problem are introduced. We study the online strategies REPLAN and IGNORE. Regarding the IGNORE strategy we can show that it works almost optimal under high load with high probability. KW - Dial-a-Ride problem on trees KW - probabilistic analysis KW - online algorithms Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10114 ER - TY - THES A1 - Krumke, Sven T1 - Online Optimization: Competitive Analysis and Beyond N2 - 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. T3 - ZIB-Report - 02-25 KW - competitive analysis KW - online optimization KW - online algorithm KW - approximation algorithm Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6925 ER -