Applications of a Special Polynomial Class of Tsp


Jack Brimberg, Ephraim Korach, Mokhtar Amami




A hypothetical problem which we call a “buried treasure problem” is presented where the objective is to locate m objects among N fixed equi-spaced caches in order to minimize a measure of the risk of loss. The general problem is shown to be NP- hard. However, a sub problem may be solved as a special class of TSP in O (N log N) time. Several applications are noted.