Basic HTML version of Foils prepared 15 March 1996

Foil 65 Comparison of Neural Networks for TSP and Data Decomposition

From Physical Optimization and Physical Computation CPSP713 Case studies in Computational Science -- Spring Semester 1996. by Geoffrey C. Fox
Neural Networks work well for NP-complete load balancing problem but fail for formally equivalent TSP. Why?
Label data or processes by i = 1 ... M
  • and processor nodes by p = 1 .. N = 2d
The redundant choice of NM neural (binary) variables
  • h(i,p) = 1 data point i on node p
    • = 0 otherwise
Fails for same reason as for TSP
The nonredundant choice (NO constraints in E) of Mlog2N neural variables
  • i ® P(i)
  • P(i) = Sd-1 2k h(i,k) succeeds
Þ Not all NP-complete problems are created equal

Northeast Parallel Architectures Center, Syracuse University, npac@npac.syr.edu

If you have any comments about this server, send e-mail to webmaster@npac.syr.edu.

Page produced by wwwfoil on Sun Feb 22 1998