home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / ai / neuraln / 4956 < prev    next >
Encoding:
Text File  |  1993-01-23  |  1.6 KB  |  42 lines
  1. Newsgroups: comp.ai.neural-nets
  2. Path: sparky!uunet!usc!sdd.hp.com!ux1.cso.uiuc.edu!cs.uiuc.edu!kadie
  3. From: kadie@cs.uiuc.edu (Carl M. Kadie)
  4. Subject: Re: Data for Travelling Salesman Prob Wanted...
  5. Message-ID: <C19uH5.JIv@cs.uiuc.edu>
  6. Organization: University of Illinois, Dept. of Comp. Sci., Urbana, IL
  7. References: <1993Jan21.114216.1196@uoft02.utoledo.edu> <C17ty4.42p@cs.uiuc.edu> <uh311ae.727724965@sunmanager> <C19rLG.FFx@cs.uiuc.edu>
  8. Date: Fri, 22 Jan 1993 20:05:29 GMT
  9. Lines: 31
  10.  
  11. uh311ae@sunmanager.LRZ-Muenchen.DE (Henrik Klagges) writes:
  12.  
  13. [...]
  14. check out the paper by fritzke in the /pub/neuroprose archive at the aftp
  15. server archive.cis.ohio-state.edu. He has a very slick 'cell-based' alg.
  16. on TSP that has excellent scaling behaviour.
  17. [...]
  18.  
  19. From looking at the paper, it looks as though the Fritzke's program
  20. doesn't guarantee the quality of its solution. Based on the _Discover_
  21. article, I think the Johnson's method can. Also, Johnson's program
  22. seems to be 2 or 3 orders of magnitude faster and to produce better
  23. solutions.  For comparison:
  24.  
  25.                Johnson                           Fritzke
  26. # of cites:    1000000                           2392
  27. CPU time:      3 cpu hours                       1.13 cpu hours
  28. Quality:       within 2% of optimum              about 9% of optimum
  29. Guaranteed
  30.  error bounds: yes (I think)                     no
  31.  
  32. - Carl
  33.  
  34. Sources: _Discover_ magazine, Jan. 1992, p 91
  35.          anonymous ftp
  36.             archive.cis.ohio-state.edu/pub/neuroprose/fritzke.linear-tsp.ps.Z
  37.  
  38.  
  39. -- 
  40. Carl Kadie -- I do not represent any organization; this is just me.
  41.  = kadie@cs.uiuc.edu =
  42.