Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!psuvax1!rutgers!mit-eddie!bbn.com!archive.bbn.com!aboulang
From: aboulang@bbn.com (Albert Boulanger)
Newsgroups: comp.theory
Subject: Re: Solution of TSP - P=NP now very probable ?
Message-ID: <ABOULANG.91Mar23163344@taurus.bbn.com>
Date: 23 Mar 91 21:33:44 GMT
References: <1991Mar20.133401.24801@ira.uka.de>
Sender: news@bbn.com
Reply-To: aboulanger@bbn.com
Organization: BBN, Cambridge MA
Lines: 14
In-reply-to: braun@ira.uka.de's message of 20 Mar 91 13:34:01 GMT


  In the german newspaper "Die Zeit" (March 14, 1991) Th. von Randow
  reported on recent work of Donald L. Miller and Joseph F. Penky on the
  Travelling Salesman Problem. Von Randow claims that they have made a big
  step towards the solution of TSP by discovering a polynomial algorithm
  for an important special case of TSP. Furthermore von Randow even suggests that
  P=NP became much more probable by their work.
  Does anybody know more details about the problem they really solved ?

Here is the paper reference:

"Exact Solution of Large Asymmetric Traveling Salesman Problems"
Donald Miller & Joseph Pekny
Science, Vol 251, 15 Feb 1991, 754-761