A hard dial-a-ride problem that is easy on average

被引：5

作者：

Coja-Oghlan, A

Krumke, SO ^{[1
]}

Nierhoff, T

机构：

[1] Univ Kaiserslautern, Dept Math, D-67653 Kaiserslautern, Germany

[2] Humboldt Univ, Inst Informat, D-10099 Berlin, Germany

来源：

JOURNAL OF SCHEDULING | 2005年 / 8卷 / 03期

关键词：

average-case analysis; NP-hard; approximation algorithm;

D O I：

10.1007/s10951-005-6811-3

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

In the dial-a-ride-problem (DARP) objects have to be moved between given sources and destinations in a transportation network by means of a server. The goal is to find the shortest transportation for the server. We study the DSRP when the underlying transportation network forms a caterpillar. This special case is strongly NP-hard in the worst case. We prove that in a probabilistic setting there exists a polynomial time algorithm that finds an optimal solution with high probability. Moreover, with high probability the optimality of the solution found can be certified efficiently. In addition, we examine the complexity of the DARP in a semirandom setting and in the unweighted case.

引用

页码：197 / 210

页数：14

共 23 条

[1]

Alimonti P, 1997, LECT NOTES COMPUT SC, V1203, P288

[2]

[Anonymous], 1968, An introduction to probability theory and its applications

[3]

Ascheuer N, 2000, LECT NOTES COMPUT SC, V1770, P639

[4] EFFICIENT SOLUTIONS TO SOME TRANSPORTATION PROBLEMS WITH APPLICATIONS TO MINIMIZING ROBOT ARM TRAVEL [J].