Brimberg, Jack; Korach, Ephraim; Amami, Mokhtar Applications of a special polynomial class of TSP. (English) Zbl 1274.90297 Yugosl. J. Oper. Res. 15, No. 1, 5-14 (2005). Summary: A hypothetical problem which we call a “buried treasure problem” is presented where the objective is to locate m objects among \(N\) fixed equispaced 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. MSC: 90C27 Combinatorial optimization 90C60 Abstract computational complexity for mathematical programming problems Keywords:partition problem; traveling salesman problem; pyramidal tours PDFBibTeX XMLCite \textit{J. Brimberg} et al., Yugosl. J. Oper. Res. 15, No. 1, 5--14 (2005; Zbl 1274.90297) Full Text: DOI