文献类型：期刊文献

中文题名：极小化总加权完工时间的Dial-a-Ride问题的在线随机算法(英文)

英文题名：ON-LINE RANDOMIZED ALGORITHM TO MINIMIZE WEIGHTED COMPLETION TIME FOR DIAL-A-RIDE PROBLEMS

作者：鲁习文[1]

机构：[1]华东理工大学理学院数学系,上海200237

年份：2004

卷号：19

期号：B12

起止页码：535

中文期刊名：高校应用数学学报（A辑）

外文期刊名：Applied Mathematics A Journal of Chinese Universities(Ser.A)

收录：CSTPCD;;北大核心:【北大核心2000】；CSCD:【CSCD2011_2012】；

语种：中文

中文关键词：在线;随机算法;dial-a-ride;竞争比

外文关键词：on-line,randomized algorithm, dial-a-ride,competitive ratio.

摘要：讨论一般度量空间上带单服务器的极小化总加权完工时间在线Dial-a-Ride问题.通过应用贪婪区间的技巧,提出了一个一般在线随机算法.根据这个算法,对于容量为1或者任意容量的一般度量空间上的在线Dial-a-Ride问题能得到一个竞争比为(2+2)/ln(1+2)的在线随机算法,这个算法不仅具有当前最好的竞争比,而且也改进了Krumke等人的结果.
In this paper, on-line dial-a-ride problems with a single server to minimize total weighted completion time on general metric space are considered. By applying technique of greedy intervals a general on-line randomized algorithms is proposed. Based on general algorithms,an on-line randomized algorithm which is 2＋√2/In（1＋√2）-competitive dial-a-ride problems on general metric space with capacity 1 or any finite capacity is obtained. The algorithm not only has the best competitive ratio possible so far,but also generalizes the results of S. O. Krumke, et al.