Paper Info
Title
On the computational complexity of the Probabilistic Traveling Salesman Problem with Deadlines.
Abstract
The Probabilistic Traveling Salesman Problem with Deadlines (PTSPD) is a stochastic vehicle routing problem considering time dependencies in terms of deadlines. The evaluation of the PTSPD objective function is believed to be a computationally demanding task and all efforts to find a polynomial time approach have failed so far. On the other hand, no hardness results regarding the evaluation of the PTSPD objective function are known. We fill this gap and show that the evaluation of the PTSPD objective function is indeed a computationally demanding task: even for Euclidean instances this task is #P-hard. We then derive additional hardness results for different computational tasks related to the PTSPD. Among other results, we show that the decision variant and the optimization variant of the PTSPD are both #P-hard. Following this, we focus on polynomial time approximations of the PTSPD objective function. We prove the existence of an FPRAS under certain conditions and examine the approximation guarantees obtained by the existing approaches. Finally, we give a strong inapproximability result regarding the objective function of a slightly more general problem, the Dependent PTSPD.
Year
DOI
Venue
2014
10.1016/j.tcs.2013.11.028
Theoretical Computer Science
Keywords
DocType
Volume
Stochastic combinatorial optimization,Stochastic vehicle routing,Computational complexity,Inapproximability
Journal
540
ISSN
Citations 
PageRank 
0304-3975
3
0.39
References 
Authors
14
1
Name
Order
Citations
PageRank
Dennis Weyland11088.43