Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. On an online traveling repairman problem with flowtimes: Worstcase and averagecase analysis
 Ngo, H.Q.: Computing and combinatorics. 15th annual international conference, COCOON 2009 : Niagara Falls, NY, USA, July 1315, 2009; Proceedings Berlin: Springer, 2009 (Lecture Notes in Computer Science 5609) ISBN: 3642028810 ISBN: 9783642028816 ISSN: 03029743 S.168177 
 Annual International Computing and Combinatorics Conference (COCOON) <15, 2009, Niagara Falls/NY> 

 Englisch 
 Konferenzbeitrag 
 Fraunhofer IVI () 
Abstract
We consider an online problem where a server operates on an edgeweighted graph C and an adversarial sequence of requests to vertices is released over time. Each request requires one unit of servicetime. The server is free to choose the ordering of service and intends to minimize the total flowtime of the requests. A natural class of algorithms for this problem are IGNORE algorithms. From worstcase perspective we show that IGNORE algorithms are not competitive for flowtime minimization. From an averagecase point of view, we obtain a more detailed picture. In our model, the adversary may still choose the vertices of the requests arbitrarily. But the arrival times are according to a stochastic process (with some rate lambda > 0), chosen by the adversary out of a natural class of processes. The class contains the Poissonprocess and (some) deterministic arrivals as special cases. We then show that there is an IGNORE algorithm that is competitive if and only if lambda not equal 1. Specifically, for lambda not equal 1, the expected competitive ratio of the algorithm is within a constant of the length of a shortest cycle that visits all vertices of G. The reason for this is that if lambda not equal 1 the requests either arrive slow enough for our algorithm or too fast even for an offline optimal algorithm. For lambda = 1 the routingmistakes of the online algorithm accumulate just as in the worst case. As an additional result, we show how IGNORE tours are constructed optimally in polynomial time, if the underlying graph G is a line.