极小化总加权完工时间的Dial-a-Ride问题的在线随机算法

摘要：

讨论一般度量空间上带单服务器的极小化总加权完工时间在线Dial-a-Ride问题.通过应用贪婪区间的技巧,提出了一个一般在线随机算法.根据这个算法,对于容量为1或者任意容量的一般度量空间上的在线Dial-a-Ride问题能得到一个竞争比为(2+√2)/ln(1+√2)的在线随机算法,这个算法不仅具有当前最好的竞争比,而且也改进了Krumke等人的结果.

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

所属期刊栏目：19

分类号：O223(运筹学)

在线出版日期：2005-09-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：535-542