%0 Journal Article
%T Two Online Algorithms for the Ambulance Systems
%A Sui Yuefei
%A <br>眭跃飞
%J 计算机科学技术学报
%D 2001
%I 
%X 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<bj, 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<bj, 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.
%K online algorithm
%K k-server problem
%K competitive analysis<br>因特网
%K 信息流
%K 处理器
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=FC5D026656E9F026C275E97FC057AC46&yid=14E7EF987E4155E6&vid=7801E6FC5AE9020C&iid=0B39A22176CE99FB&sid=2B25C5E62F83A049&eid=2B25C5E62F83A049&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=1&reference_num=5