Two Online Algorithms for the Ambulance Systems

Two online algorithms for the ambulance systems

An ambulance system consists of a collectionS={s ₁,...s_m} 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<b_j, whered _i,j is the distance between emergency centers _i and patientr _j, andv is the velocity of ambulance. A fault of algorithmA is such that to a request for ambulance at some timet _j withj≤n, for everyi withd _i,j/v<b_j, there is no ambulance available ins _i. The cost of an algorithmA is the number of faultsA makes. This paper gives two algorithmsB andC, whereB is the local greedy algorithm andC is a variant of balancing costs, and proves that bothB andC have no bounded competitive ratios. Moreover, given any sequence σ of requests for ambulances without optimal faults, the cost ofC on σ is less than or equal to n/3] and that ofB is less than or equal to n/2]. The project was partially supported by the National Natural Science Foundation of China (No.69673017). SUI Yuefei was born in 1963. He received the Ph.D. degree in mathematics from the Institute of Software, The Chinese Academy of Sciences in 1988. He is a professor of the Institute of Software, The Chinese Academy of Sciences. His current research interests include recursion theory, theory of computability, complexity of computation, and rough set theory.