：We present three open combinatorial optimization problems from the standpoint of competitive analysis, in the case that there is no complete information.
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...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].展开更多
基金This work is supported by NSF of China and Shandong Province and The Grant of Young and Middle-age Scientists in Shandong Provi
文摘：We present three open combinatorial optimization problems from the standpoint of competitive analysis, in the case that there is no complete information.
基金the National Natural Science Foundation of China (No.69673017).
文摘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].
