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., and Kravchuk, D.N., "Minimum of a linear form on the set of all complete cycles of the symmetric group Sn", Cybernetics, 4 (1968) 52-53.

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

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

Burkard, R.E., Deineko, V.G., Van Dal, R., Van Der Veen, J.A.A., and Woeginger, G.J., "Well-solvable special cases of the Traveling Salesman Problem: a survey", SIAM Review, 40 (1998) 496-546.

Garey, M.R., and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP Completeness, Freeman and Company, New York, 1979.

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

Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B., The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, New York, 1990.

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

Downloads

Published

2005-03-01

Issue

Vol. 15 No. 1 (2005)

Section

Research Articles

License

Copyright (c) 2005 YUJOR

Creative Commons License

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