Die beiden Arbeiten Testing the necklace condition for shortest tours and optimal factors in the plane und The N-line traveling salesman problem untersuchen Spezialfälle des euklidischen Rundreiseproblems in der Ebene, die in polynomieller Zeit gelöst werden können. In meiner Dissertation Two solvable cases of the traveling salesman problem habe ich Ergebnisse aus diesen beiden Arbeiten zusammengefasst. Dabei habe ich die Ergebnisse über die "Halskettenbedingung" (necklace condition) erweitert, indem ich gezeigt habe, dass jeder Graph einer Familie von Graphen, die auf geometrische Art definiert ist, durch Wegnahme von O(SQRT (n)) Knoten in zwei annähernd gleich große Teile getrennt werden kann. Diese Graphen beschreiben die Struktur des Gleichungs- und Ungleichungssystems, das zum Überprüfen der Halskettenbedingung gelöst werden muss. Mit Hilfe dieser Trennungseigenschaft kann man das System mit der Methode "generalized nested dissection", die auf Lipton und Tarjan zurückgeht, schnell lösen. In der Dissertation habe ich auch detailliert ausgeführt und analysiert, wie man bei dieser Methode den Speicherbedarf reduzieren kann.
Für einen Spezialfall des Problems aus der oben erwähnten Arbeit The N-line traveling salesman problem, nämlich das 3-Geraden-Rundreiseproblem, wurde in der Arbeit The convex-hull-and-line traveling salesman problem: A solvable case mit Vladimir Deineko und René van Dal ein besserer Algorithmus angegeben.
Die Arbeit The quadratic assignment problem with a monotone Anti-Monge and a symmetric Toeplitz matrix: easy and hard cases behandelt Spezialfälle des quadratischen Zuordnungsproblems, die in polynomialer Zeit gelöst werden können. Dazu gehören auch Rundreiseprobleme, bei denen die Kostenmatrix gewisse Bedingungen erfüllt. Nebenbei wird gezeigt, dass das sogenannte Turbinenproblem NP-schwer ist. Bei diesem Problem soll man vorgegebene Massen auf den Ecken eines regelmäßigen Vielecks so anordnen, dass der Schwerpunkt möglichst nahe am Mittelpunkt liegt.
zum Überblick