TAILIEUCHUNG - Applications of a special polynomial class of TSP
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 NPhard. However, a sub problem may be solved as a special class of TSP in O (N log N) time. Several applications are noted. | Yugoslav Journal of Operations Research 15 (2005), Number 1, 5-14 APPLICATIONS OF A SPECIAL POLYNOMIAL CLASS OF TSP Jack BRIMBERG, Royal Military College of Canada, CP17000 Stn Forces Kingston, Ontario, Canada K7K 7B4 Ephraim KORACH Ben-Gurion University of the Negev, Beer-Sheva, Israel Mokhtar AMAMI Royal Military College of Canada, CP17000 Stn Forces Kingston, Ontario, Canada K7K 7B4 Presented at XXX Yugoslav Simposium on Operations Research Received: January 2004 / Accepted: January 2005 Abstract: 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 NPhard. However, a sub problem may be solved as a special class of TSP in O (N log N) time. Several applications are noted. Keywords: Partition problem, traveling salesman problem, pyramidal tours. 1. INTRODUCTION A fictional scenario is presented which we term a “buried treasure problem”. The objective is to partition and locate m objects of value among N secret caches in order to minimize a measure of the risk of loss. Under the model assumptions, the general problem is shown to be reducible to the partition problem which is NP-complete (., Garey and Johnson (1979), p. 60-61; Simeone (1986)). However, for a specified partitioning of the set of objects, the assignment of subsets to the individual caches may be formulated as a special class of traveling salesman problem (TSP), and solved in polynomial time. 6 J. Brimberg, E. Korach, M. Amami / Applications of a Special Polynomial Class of TSP The distance matrix of the formulated TSP is shown to possess the anti-Monge property (., see Burkard et al. (1995) for a definition). For a general Monge matrix, it is well known that an optimal tour may be constructed with a pyramidal sequence in O(N2) operations using dynamic programming (see Lawler, Lenstra, Rinnooy Kan .
đang nạp các trang xem trước
