OSA's Digital Library

Optics Express

Optics Express

  • Editor: C. Martijn de Sterke
  • Vol. 15, Iss. 20 — Oct. 1, 2007
  • pp: 12627–12627
« Show journal navigation

An optical solution for the traveling salesman problem: erratum

Tobias Haist and Wolfgang Osten  »View Author Affiliations


Optics Express, Vol. 15, Issue 20, pp. 12627-12627 (2007)
http://dx.doi.org/10.1364/OE.15.012627


View Full Text Article

Acrobat PDF (16 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

The initialization time for setting up the experiment grows exponential with the number of cities. Therefore the overall time required to solve the problem is not quadratic but exponential.

© 2007 Optical Society of America

In [1

1. T. Haist and W. Osten, “An optical solution for the traveling salesman problem,” Opt. Express 15, 10473–10482 (2007) [CrossRef] [PubMed]

] we claimed that the proposed gedankenexperiment will find the global solution of a traveling salesman problem (TSP) in quadratic time. That means the time required to solve the TSP increases quadratic with the number of cities N. Our analysis was based on the number of measurements needed to determine the minimum path.

However we did not consider in this estimation that the first measurement only can start after the light has passed through the network. Since the delays for our chosen labeling scheme (Eq. 1 in [1

1. T. Haist and W. Osten, “An optical solution for the traveling salesman problem,” Opt. Express 15, 10473–10482 (2007) [CrossRef] [PubMed]

]) were chosen to be ∼ 2i for city i we have an exponential increase of the overall path length for the light to travel. Therefore the initialization time required before the measurements really can start also increases exponentially with N. That is we have an increase in the initialization time of O(2N). This is considerably lower than the original cost of O(N!) ∼ O(NN) and from a practical point of view this initialization cost is low (due to the high speed of photons) for small problems. Nevertheless the chosen delay settings won’t lead to an overall reduction to quadratic time. This important fact has to be considered.

References and links

1.

T. Haist and W. Osten, “An optical solution for the traveling salesman problem,” Opt. Express 15, 10473–10482 (2007) [CrossRef] [PubMed]

2.

M. Oltean, “A light-based device for solving the Hamiltonian path problem,” in Lecture Notes in Computer Science 4135, 217–227, Springer (2006). [CrossRef]

3.

M. Oltean, “Solving the Hamiltonian path problem with a light-based computer,” Natural Computing, to appear in Vol. 6, Issue 4, 2007.

4.

S. Dolev and H. Fitoussi, “The traveling beams optical solutions for bounded NP-Complete problems,” in Lecture Notes in Computer Science 4475, 120–134 (2007). [CrossRef]

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: September 5, 2007
Manuscript Accepted: September 13, 2007
Published: September 17, 2007

Citation
Tobias Haist and Wolfgang Osten, "An optical solution for the traveling salesman problem: erratum," Opt. Express 15, 12627-12627 (2007)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-15-20-12627


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. T. Haist and W. Osten, "An Optical Solution For The Traveling Salesman Problem," Opt. Express 15, 10473-10482 (2007) [CrossRef] [PubMed]
  2. M. Oltean, "A light-based device for solving the Hamiltonian path problem," in Lecture Notes in Computer Science 4135, 217-227, Springer (2006). [CrossRef]
  3. M. Oltean, "Solving the Hamiltonian path problem with a light-based computer," Natural Computing, to appear in Vol. 6, Issue 4, 2007.
  4. S. Dolev and H. Fitoussi, "The traveling beams optical solutions for bounded NP-Complete problems," in Lecture Notes in Computer Science 4475, 120-134 (2007). [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.


« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited