Seminario Interdipartimentale di Algoritmica
 
 

DI - Department of Computer Science
Seminar Room, third floor

Abstract:

In several circumstances we have to solve a problem whose instance is not completely known in advance. Situations of this kind occur in computer systems and networks management, in financial decision making, in robotics etc. Problems of this kind are called on-line problems. In most applications (e.g. paging) an agent is required to serve requests in an on line fashion and a request has to be served by the agent before a new request is revealed. In such cases the notion of time is simply used to refer to a totally ordered sequence of discrete instants. Both requests and agent's service actions occur instantanaously in one of these moments. The actual time intercurring between two instants is not specified and inessential under any respect. A different situation occurs instead in other problems where the time dimension is continuous and plays a specific role. We call this kind of problems real time on-line problems. In this paper we address a specific class of real time on-line problems: vehicle routing problems. By examining the properties of this paradigmatic type of problems, we put in evidence the role of real time in the design of competitive algorithms, in the construction of adversarial arguments and in the definition of clairvoyancy.

Joint work with L. Allulli, V. Bonifaci, and L. Laura.