Article View: comp.theory
Article #1941Re: Suggstion: (was: Re: P=NP; the proof)
From: Gordon Royle
Date: Tue, 12 Jan 1993 07:24
Date: Tue, 12 Jan 1993 07:24
17 lines
1326 bytes
1326 bytes
In <pcw.726468672@digex> pcw@access.digex.com (Peter Wayner) writes: >core of the problem. We already have neat algorithms that get close to >the right answer on NP-complete problems like the travelling salesman. >For all practical intents and realistic purposes, this is enough.It's >really just an academic question now. Is this true? I am not aware of any decent algorithms for Travelling Salesman at all. In fact G&J show that there cannot be any polynomial time approximation algorithms for Travelling Salesman that achieve ANY given multiple of the optimal solution (page 147). Does this not contradict the above statement, or am I labouring under a delusion? Gordon
Technical Details
Message-ID:
<gordon.726823495@ningaui>Path:
arc1-ca.pugleaf.net!sparky!uunet!munnari.oz.au!uniwa!bilby.cs.uwa.oz.au!ningaui!gordonReferences:
<1idr1nINNrl@nunki.anu.edu.au> <1ifcmpINN11k@nunki.anu.edu.au> <1ifljqINN137@nunki.anu.edu.au> <1iicnjINNloe@uwm.edu> <pcw.726468672@digex>Show Full Headers
Complete Article Headers
Newsgroups: comp.theory Path: arc1-ca.pugleaf.net!sparky!uunet!munnari.oz.au!uniwa!bilby.cs.uwa.oz.au!ningaui!gordon From: gordon@cs.uwa.oz.au (Gordon Royle) Subject: Re: Suggstion: (was: Re: P=NP; the proof) Message-ID: <gordon.726823495@ningaui> Keywords: Collapse of hierarchy Sender: usenet@bilby.cs.uwa.edu.au Nntp-Posting-Host: ningaui Organization: Dept. Computer Science, University of Western Australia. References: <1idr1nINNrl@nunki.anu.edu.au> <1ifcmpINN11k@nunki.anu.edu.au> <1ifljqINN137@nunki.anu.edu.au> <1iicnjINNloe@uwm.edu> <pcw.726468672@digex> Distribution: inet Date: Tue, 12 Jan 1993 07:24:55 GMT Lines: 18