OSA's Digital Library

Applied Optics

Applied Optics

APPLICATIONS-CENTERED RESEARCH IN OPTICS

  • Editor: James C. Wyant
  • Vol. 46, Iss. 5 — Feb. 10, 2007
  • pp: 711–724

Optical solution for bounded NP-complete problems

Natan T. Shaked, Stephane Messika, Shlomi Dolev, and Joseph Rosen  »View Author Affiliations


Applied Optics, Vol. 46, Issue 5, pp. 711-724 (2007)
http://dx.doi.org/10.1364/AO.46.000711


View Full Text Article

Enhanced HTML    Acrobat PDF (3017 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

We present a new optical method for solving bounded (input-length-restricted) NP-complete combinatorial problems. We have chosen to demonstrate the method with an NP-complete problem called the traveling salesman problem (TSP). The power of optics in this method is realized by using a fast matrix–vector multiplication between a binary matrix, representing all feasible TSP tours, and a gray-scale vector, representing the weights among the TSP cities. The multiplication is performed optically by using an optical correlator. To synthesize the initial binary matrix representing all feasible tours, an efficient algorithm is provided. Simulations and experimental results prove the validity of the new method.

© 2007 Optical Society of America

OCIS Codes
(070.2580) Fourier optics and signal processing : Paraxial wave optics
(070.4550) Fourier optics and signal processing : Correlators
(070.4560) Fourier optics and signal processing : Data processing by optical means
(200.0200) Optics in computing : Optics in computing

ToC Category:
Fourier Optics and Optical Signal Processing

History
Original Manuscript: March 15, 2006
Revised Manuscript: September 10, 2006
Manuscript Accepted: October 11, 2006
Published: January 25, 2007

Citation
Natan T. Shaked, Stephane Messika, Shlomi Dolev, and Joseph Rosen, "Optical solution for bounded NP-complete problems," Appl. Opt. 46, 711-724 (2007)
http://www.opticsinfobase.org/ao/abstract.cfm?URI=ao-46-5-711


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. D. Harel, Algorithmics: The Spirit of Computing (Addison-Wesley, 1987).
  2. G. Reinelt, The Traveling Salesman: Computational Solutions for TSP Applications (Springer-Verlag, 1994).
  3. J. E. Mitchell, "Branch-and-cut algorithms for combinatorial optimization problems," in Handbook of Applied Optimization (Oxford U. Press, 2002), pp. 65-77.
  4. K. A. Smith, "Neural networks for combinatorial optimization: a review of more than a decade of research," INFORMS J. Comput. 11, 15-34 (1999). [CrossRef]
  5. N. Collings, R. Sumi, K. J. Weible, B. Acklin, and W. Xue, "The use of optical hardware to find good solutions of the travelling salesman problem (TSP)," in Proc. SPIE 1806, 637-641 (1993). [CrossRef]
  6. D. Gutfreund, R. Shaltiel, and A. Ta-Shma, "If NP languages are hard on the worst-case then it is easy to find their hard instances," in Proceedings of the 20th Annual Conference on Computational Complexity (CCC) (2005). A long version of this paper is available on the web at http://www.cs.tau.ac.il/∼amnon/Papers/GST.cc05.journal.ps.
  7. J. W. Goodman, Introduction to Fourier Optics, 2nd ed. (McGraw-Hill, 1996), pp. 232-246.
  8. C. S. Weaver and J. W. Goodman, "A technique for optically convolving two functions," Appl. Opt. 5, 1248-1249 (1966). [CrossRef] [PubMed]
  9. A. VanderLugt, "Signal detection by complex spatial filtering," IEEE Trans. Inf. Theory IT-10, 139-145 (1964). [CrossRef]
  10. A. Homaifar, S. Guan, and G. E. Liepins, "Schema analysis of the traveling salesman problem using genetic algorithms," Complex Syst. 6, 183-217 (1992).
  11. D. G. Feitelson, Optical Computing: A Survey for Computer Scientists (MIT Press, 1988), pp. 148-163.
  12. M. A. Karim and A. A. S. Awwal, Optical Computing: An Introduction (Wiley, 1992), pp. 328-356.
  13. J. W. Goodman, Introduction to Fourier Optics, 2nd ed. (McGraw-Hill, 1996), pp. 282-289.
  14. A. D. McAulay, Optical Computer Architectures: The Application of Optical Concepts to Next Generation Computers (Wiley, 1991), pp. 289-299. [PubMed]
  15. S. Dolev, E. Korach, and G. Uzan, "A method for encryption and decryption of messages," PCT patent application WO 2006/001006 (5 January 2006).

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