home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2861 < prev    next >
Encoding:
Text File  |  1993-01-12  |  1.3 KB  |  33 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!munnari.oz.au!uniwa!bilby.cs.uwa.oz.au!ningaui!gordon
  3. From: gordon@cs.uwa.oz.au (Gordon Royle)
  4. Subject: Re: Suggstion: (was: Re: P=NP; the proof)
  5. Message-ID: <gordon.726823495@ningaui>
  6. Keywords: Collapse of hierarchy
  7. Sender: usenet@bilby.cs.uwa.edu.au
  8. Nntp-Posting-Host: ningaui
  9. Organization: Dept. Computer Science, University of Western Australia.
  10. References: <1idr1nINNrl@nunki.anu.edu.au> <1ifcmpINN11k@nunki.anu.edu.au> <1ifljqINN137@nunki.anu.edu.au> <1iicnjINNloe@uwm.edu> <pcw.726468672@digex>
  11. Distribution: inet
  12. Date: Tue, 12 Jan 1993 07:24:55 GMT
  13. Lines: 18
  14.  
  15. In <pcw.726468672@digex> pcw@access.digex.com (Peter Wayner) writes:
  16.  
  17. >core of the problem. We already have neat algorithms that get close to
  18. >the right answer on NP-complete problems like the travelling salesman.
  19. >For all practical intents and realistic purposes, this is enough.It's
  20. >really just an academic question now.
  21.  
  22.  
  23. Is this true? I am not aware of any decent algorithms for Travelling 
  24. Salesman at all. In fact G&J show that there cannot be any polynomial
  25. time approximation algorithms for Travelling Salesman that achieve
  26. ANY given multiple of the optimal solution (page 147).   
  27. Does this not contradict the above statement, or am I labouring under a 
  28. delusion? 
  29.  
  30.  
  31. Gordon
  32.  
  33.