Two Online Algorithms for the Ambulance Systems

An ambulance system consists of a collectionS={s 1,...sm} of emergency centers in a metric spaceM. Each emergency centers i has a positive integral capacityc i to denote, for example, the number of ambulances at the center. There aren = Σ i = 1 m c i patients requiring ambulances at different timest j and every patient is associated with a numberb j, the longest time during which the patient can wait for ambulance. An online algorithmA will decide which emergency center sends an ambulance to serve a request for ambulance from a patient at some time. If algorithmA sends an ambulance ins i to serve a patientr j, then it must be observed thatd i,j/v