论文部分内容阅读
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
其他文献
目的 优化苎麻叶中绿原酸超声提取工艺.方法 利用单因素实验确定苎麻叶中绿原酸超声提取工艺条件的响应面中心值,通过响应面法和MATLAB7.0对提取工艺条件进行优化.结果 优化
Information filtering (IF) systems are important for personalized information service. However, most current IF systems suffer from low quality and long trainin
请下载后查看,本文暂不支持在线获取查看简介。
Please download to view, this article does not support online access to view profile.
期刊
阅读是我们进行语文学习的基础,要想提高我们的语文水平,平时就要加强阅读,但目前很多学生不重视阅读,教师也缺乏课堂课外的阅读指导,导致学生阅读能力差,阅读效率也不高。所
期刊
该文从挂篮荷载计算、施工流程、支座及临时固结施工、挂篮安装及试验、合拢段施工、模板制作安装、钢筋安装、混凝土的浇筑及养生、测量监控等方面人手,介绍了S226海滨大桥
期刊
目的:探讨促排卵治疗中多卵泡发育者的处理方法。方法:对于克罗米酚(CC)或hMG促排卵中发生多卵泡发育的30例患者,分别随机采用IVF-ET(A组)或成熟卵泡刺破+多余卵泡抽吸+宫腔
该文从挂篮荷载计算、施工流程、支座及临时固结施工、挂篮安装及试验、合拢段施工、模板制作安装、钢筋安装、混凝土的浇筑及养生、测量监控等方面人手,介绍了S226海滨大桥
期刊