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


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.


spatial and temporal reasoning; complexity

Full Text: PDF