AAAI Publications, Tenth Symposium of Abstraction, Reformulation, and Approximation

Font Size: 
On the Traveling Salesman Problem with Simple Temporal Constraints
T. K. Satish Kumar, Marcello Cirillo, Sven Koenig

Last modified: 2013-06-19

Abstract


Many real-world applications require the successful combination of spatial and temporal reasoning. In this paper, we study the general framework of the Traveling Salesman Problem with Simple Temporal Constraints. Representationally, this framework subsumes the Traveling Salesman Problem, Simple Temporal Problems, as well as many of the frameworks described in the literature. We analyze the theoretical properties of the combined problem providing strong inapproximability results for the general problem, and positive results for some special cases.

Full Text: PDF