On-Line Algorithms, Real Time, the Virtue of Laziness, and the Power of Clairvoyance

摘要

In this paper we showed some peculiar characteristics of on-line real time problems, using the large class of vehicle routing problems to introduce them. We presented an overview of some results related to the OL-TSP; in particular we considered the homing and nomadic version where the objective function is the completion time, together with the L-OL-TRP, where the goal is to minimize the latency. We also mentioned the more general OL-A-TSP, where the underlying space does not satisfy the symmetry property. Quite surprisingly, in all the above problems being a zealous server is not a winning strategy: waiting for more requests to show up can provide a better picture of "what is going on". Is this a common trait of on-line real time problems? Intuitively, this might be the case only for the problems in which serving one request can affect the quality of service of the following ones; in vehicle routing problems, for example, moving the server far away from the origin could prevent a fast answer to new requests. We mentioned several types of lookahead; amongst them, the more natural and more effective, for these problems, is undoubtedly time lookahead; indeed, time lookahead can lead to a deeper understanding of the role of real time in the problem. Furthermore, in several practical applications it is natural to assume the availability of some amount of time lookaehad. We also addressed other alternative models of information disclosure over time like clairvoyance and the restricted information model. We believe it is still missing a formal framework to analyze and study on-line real time problems, whose relevance is justified by the huge variety of real world practical applications that they can model; we made a first step towards this direction by emphasizing some of their common and distinctive aspects.