braun@ira.uka.de (Heinz Braun) (03/20/91)
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 ? Heinrich Braun Institut fuer Logik, Komplexitaet und Deduktionssysteme Universitaet Karlsruhe Postfach 6980 D 7500 Karlsruhe (FRG) email: braun@ira.uka.de
aboulang@bbn.com (Albert Boulanger) (03/24/91)
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