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

• 作者: 鲁习文
• 来源期刊: 高校应用数学学报A辑
• 学科: 数学
• 关键词: 在线 随机算法 dial-a-ride 竞争比
• 年，卷（期）: 2004,（z1）
• 页码范围: 535-542
• 页数: 8页
• 分类号: O223
• 字数: 1057字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-4424.2004.z1.005

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	鲁习文	华东理工大学理学院数学系	29	71	6.0	6.0