braun@ira.uka.de (Heinz Braun) (03/22/91)
Heinrich Braun Institut fuer Logik, Komplexitaet und Deduktionssysteme Universitaet Karlsruhe Postfach 6980 D 7500 Karlsruhe (FRG) email: braun@ira.uka.de
braun@ira.uka.de (Heinz Braun) (03/22/91)
Summary: There is an article in Science, Vol. 251, p.754-761 by Miller/Pekny: "Exact Solution of Large Asymmetric Traveling Salesman Problems" . They report that their algorithm has solved random asymmetric TSPs with up to 500 000 cities. Unfortunately the algorithm was confounded by small symmetric problems where it only solved TSPs with atmost 30 cities in acceptable time. Furthermore the biggest solved practical problem (asymmetr.) had only 100 cities. So their results seem just to suggest that the average time complexity of the asymmetric TSP is linearly bounded. But the comment in "DIE ZEIT" that therefore the TSP is nearly solved is overoptimistic. Many thanks for comments and pointing out the reference to Bjorn Ellertsson Cameron Laird and Art Werschulz. Heinrich Braun Institut fuer Logik, Komplexitaet und Deduktionssysteme Universitaet Karlsruhe Postfach 6980