Two Online Algorithms for the Ambulance Systems

An ambulance system consists of a collection S=S1,……Sm ofemergency centers in a metric space M. Each emergency centerSi has a positive integral capacity Ci to denote, for example, thenumber of ambulances at the center. There are n=sumI=1^m cipatients requiring ambulances at different times Tj and every patientis associated with a number Bj, the longest time during which thepatient can wait for ambulance. An online algorithm A willdecide which emergency center sends an ambulance to serve a request forambulance from a patient at some time. If algorithm A sends anambulance in Si to serve a patient Rj, then it must be observedthat dI,j/v