home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2862 < prev    next >
Encoding:
Internet Message Format  |  1993-01-12  |  2.5 KB
  1. Path: sparky!uunet!munnari.oz.au!spool.mu.edu!howland.reston.ans.net!usc!rpi!ghost.dsi.unimi.it!univ-lyon1.fr!chx400!sicsun!disuns2!/!diderich
  2. From: diderich@di.epfl.ch (Claude Diderich)
  3. Newsgroups: comp.theory
  4. Subject: Re: Suggstion: (was: Re: P=NP; the proof)
  5. Keywords: Collapse of hierarchy
  6. Message-ID: <1993Jan12.135311@di.epfl.ch>
  7. Date: 12 Jan 93 12:53:11 GMT
  8. References: <1idr1nINNrl@nunki.anu.edu.au> <1ifcmpINN11k@nunki.anu.edu.au> <1ifljqINN137@nunki.anu.edu.au> <1iicnjINNloe@uwm.edu> <pcw.726468672@digex> <gordon.726823495@ningaui>
  9. Sender: news@disuns2.epfl.ch
  10. Organization: Ecole Polytechnique Federale de Lausanne
  11. Lines: 39
  12. Nntp-Posting-Host: disun50.epfl.ch
  13.  
  14. In article <gordon.726823495@ningaui>, gordon@cs.uwa.oz.au (Gordon Royle) writes:
  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. Peter Wayer's statement is not true. We do have algorithms that give in general
  33. good solutions for the TSP, but we cannot say anything about the quality in
  34. general of any solution produced. Indeed such algorithms may in 95% of the cases
  35. approach the optimal solution by 90%. But we cannot guarantee 100% of the cases.
  36. Furthermore, we do not have any possibility to check if a given solution is
  37. within the 95% of good solutions or not.
  38.  
  39. But TSP is not the only NP-complete problem. There are other problems like Max
  40. Clique that even cannot be approximated within any constant, e.g. approxiating is
  41. as hard as solving.
  42.  
  43. Therefore I think the P?=NP question is not ony of theoretical interesed.
  44.  
  45. Claude
  46.  
  47. ---------------------------------------------------------------------------
  48. Claude G. Diderich                            Internet: diderich@di.epfl.ch
  49. 30, Avenue S.Reymondin  --  CH-1009 Pully (VD)  --  Switzerland  --  Europe
  50.  
  51. ``Imagination is more important than knowledge''            Albert Einstein
  52. ---------------------------------------------------------------------------
  53.