摘要
An ambulance system consists of a collection S = {s1,...,sm ) sm} of emergency centers in a metric space M. Each emergency center si has a positive integral capacity ci to denote, for example, the number of ambulances at the center. There are n = =1, ci patients requiring ambulances at different times tj and every patient is associated with a number bj, the longest time during which the patient can wait for ambulance. An online algorithm A will decide which emergency center sends an ambulance to serve a request for ambulance from a patient at some time. If algorithm A sends an ambulance in si to serve a patient rj, then it must be observed that di,j/v < bj, where di,j is the distance between emergency center si and patient rj, and v is the velocity of ambulance. A fault of algorithm A is such that to a request for ambulance at some time tj with j ≤n, for every i with di,j/v < bj, there is no ambulance available in si. The cost of an algorithm A is the number of faults A makes. This paper gives two algorithms B and C, where B is the local greedy algorithm and C is a variant of balancing costs, and proves that both B and C have no bounded competitive ratios. Moreover, given any sequence a of requests for ambulances without optimal faults, the cost of C on σis less than or equal to [n/3] and that of B is less than or equal to [n/2].
An ambulance system consists of a collection S = {s1,...,sm ) sm} of emergency centers in a metric space M. Each emergency center si has a positive integral capacity ci to denote, for example, the number of ambulances at the center. There are n = =1, ci patients requiring ambulances at different times tj and every patient is associated with a number bj, the longest time during which the patient can wait for ambulance. An online algorithm A will decide which emergency center sends an ambulance to serve a request for ambulance from a patient at some time. If algorithm A sends an ambulance in si to serve a patient rj, then it must be observed that di,j/v < bj, where di,j is the distance between emergency center si and patient rj, and v is the velocity of ambulance. A fault of algorithm A is such that to a request for ambulance at some time tj with j ≤n, for every i with di,j/v < bj, there is no ambulance available in si. The cost of an algorithm A is the number of faults A makes. This paper gives two algorithms B and C, where B is the local greedy algorithm and C is a variant of balancing costs, and proves that both B and C have no bounded competitive ratios. Moreover, given any sequence a of requests for ambulances without optimal faults, the cost of C on σis less than or equal to [n/3] and that of B is less than or equal to [n/2].
基金
the National Natural Science Foundation of China (No.69673017).
