OSA's Digital Library

Optics Express

Optics Express

  • Editor: C. Martijn de Sterke
  • Vol. 15, Iss. 16 — Aug. 6, 2007
  • pp: 10473–10482

Optics InfoBase > Optics Express > Volume 15 > Issue 16 > Page 10473

An Optical Solution For The Traveling Salesman Problem

Tobias Haist and Wolfgang Osten  »View Author Affiliations


Optics Express, Vol. 15, Issue 16, pp. 10473-10482 (2007)
http://dx.doi.org/10.1364/OE.15.010473


View Full Text Article

Enhanced HTML    Acrobat PDF (174 KB)


Advanced Search

Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

We introduce an optical method based on white light interferometry in order to solve the well-known NP–complete traveling salesman problem. To our knowledge it is the first time that a method for the reduction of non–polynomial time to quadratic time has been proposed. We will show that this achievement is limited by the number of available photons for solving the problem. It will turn out that this number of photons is proportional to NN for a traveling salesman problem with N cities and that for large numbers of cities the method in practice therefore is limited by the signal–to–noise ratio. The proposed method is meant purely as a gedankenexperiment.

© 2007 Optical Society of America

OCIS Codes
(120.3180) Instrumentation, measurement, and metrology : Interferometry
(200.0200) Optics in computing : Optics in computing
(200.4740) Optics in computing : Optical processing
(260.3160) Physical optics : Interference

ToC Category:
Optics in Computing

History
Original Manuscript: June 5, 2007
Revised Manuscript: July 3, 2007
Manuscript Accepted: July 3, 2007
Published: August 3, 2007

Citation
Tobias Haist and Wolfgang Osten, "An Optical Solution For The Traveling Salesman Problem," Opt. Express 15, 10473-10482 (2007)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-15-16-10473


Sort:  Year  |  Journal  |  Reset  

References

  1. G. Laporte, A. Asef-Vaziri, and C. Sriskandarajah, "Some applications of the generalized travelling salesman problem," J. Oper. Res. Soc. 47, 1461-1467 (1996).
  2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms, (MIT Press, 2001).
  3. C. Vourdouris and E. Tsang, "Guided local search and its application to the traveling salesman problem," Eur. J. Oper. Res. 113, 80-110 (1998).
  4. C. Kirkpatrick, "Optimization by simulated annealing: Quantitative studies," J. Stat. Phys. 34, 975-986 (1984). [CrossRef]
  5. J. J. Hopfield and D. W. Tank, "Neural’ computation of decisions in optimization problems," Biol. Cybern. 52, 381-384 (1985).
  6. F. Glover, E. Taillard, and D. de Werra, "A user’s guide to tabu search," Ann. Oper. Res. 41, 3-28 (1993). [CrossRef]
  7. S. Lin and W. Kernighan, "An effective heuristic algorithm for the traveling salesman problem,’Oper. Res. 21, 498-516, (1973). [CrossRef]
  8. J. Edmonds, "Matroids and the greedy algorithm," Math. Program. 1, 127-136 (1971). [CrossRef]
  9. S. Arora, "Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems," J. ACM 45, 753-7872 (1998). [CrossRef]
  10. D. S. Johnson, and L. A. McGeoch, "The traveling salesman problem: a case study in local optimization," in Local Search in Combinatorial Optimization," E. Aarts and J. K. Lenstra, eds., (Princton University Press, 2003).
  11. T. Hogg and D. Portnov, "Quantum optimization," Inf. Sci. 128, 181-197 (2000). [CrossRef]
  12. S. Y. Shin, B. T. Zhang, B.T., and S. S. Jun, "Solving traveling salesman problems using molecular programming," in Proceedings of the Congress on Evolutionary Computation, P. Angeline, Z. Michalewicz, M. Schoenauer, X. Yao, and A. Zalzala, eds., (IEEE Press, 1999), pp 994-1000.
  13. N. T. Shaked, S. Messika, S. Dolev, and J. Rosen, "Optical solution for bounded NP-complete problems," Appl. Opt. 46, 711-724 (2007). [CrossRef] [PubMed]
  14. G. S. Kino and S. C. Chi, "Mirau correlation microscope," Appl. Opt. 29, 3775-3783 (1990). [CrossRef] [PubMed]
  15. V. A. Kozlov, J. Hernandez-Codero, and T. F. Morse, "All-fiber coherent beam combining of fiber lasers," Opt. Lett. 24, 1814-1816 (1999). [CrossRef]
  16. B. E. A. Saleh and M. C. Teich, Fundamentals of Photonics, (Wiley, 1991). [CrossRef]
  17. A. F. Fercher, W. Drexler, C. K. Hitzenberger, and T. Lasser: "Optical coherence tomography — principles and applications," Reports on Progress in Physics 66, 239-303 (2003). [CrossRef]

Cited By

 Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

Figures

Fig. 1. Fig. 2. Fig. 3.
 
Fig. 4.
 

« Previous Article

OSA is a member of CrossRef.

CrossCheck Deposited