Applications of a special polynomial class of TSP

Authors

  • Jack Brimberg Royal Military College of Canada, Ontario, Canada
  • Ephraim Korach Ben-Gurion University of the Negev, Beer-Sheva, Israel
  • Mokhtar Amami Royal Military College of Canada, Ontario, Canada

DOI:

https://doi.org/10.2298/YJOR0501005B

Keywords:

partition problem, traveling salesman problem, pyramidal tours

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 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.

References

Aizenshtat, V.S., Kravchuk, D.N. (1968) Minimum of a linear form on the set of all complete cycles of the symmetric group Sn. Cybernetics, 4, 52-53

Burkard, R.E. (1997) Efficiently solvable special cases of hard combinatorial optimization problems. Mathematical Programming, 79, 55-69

Burkard, R.E., Cela, E., Rote, G., Woeginger, G.J. (1995) The quadratic assignment problem with an Anti-Monge and a Toeplitz matrix: Easy and hard cases. Graz: Technische Universität - Institut für Mathematik B, Technical report SFB-34

Burkard, R.E., Deineko, V.G., van Dal, R., van der Veen, J.A.A., Woeginger, G.J. (1998) Well-solvable special cases of the travelling salesman problem: A survey. SIAM Review, 40, 496-546

Garey, M.R., Johnson, D.S. (1979) Computers and intractability: A guide to the theory of NP-completeness. San Francisco, CA, itd: W.H. Freeman Publishing

Hallin, M., Melard, G., Milhaud, X. (1992) Permutational extreme values of autocorrelation coefficients and a Pitman test against serial dependence. Ann Statist., 20, 523-534

Lawler, E.L., Lenstra, J.K., Rinnooy, K.A.H.G., Shmoys, D.B. (1990) The travelling salesman problem: A guided tour of combinatorial optimization. New York, itd: Wiley

Simeone, B. (1986) An asymptotically exact polynomial algorithm for equipartition problems. Discrete Applied Mathematics, 14, 283-293

Downloads

Published

2005-03-01

Issue

Vol. 15 No. 1 (2005)

Section

Research Articles

License

Copyright (c) YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.