摘要
讨论一般度量空间上带单服务器的极小化总加权完工时间在线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.
出处
《高校应用数学学报（A辑）》
CSCD
北大核心
2004年第B12期535-542,共8页
Applied Mathematics A Journal of Chinese Universities(Ser.A)
