×

Applications of a special polynomial class of TSP. (English) Zbl 1274.90297

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
PDFBibTeX XMLCite
Full Text: DOI