Das Problem des Handlungsreisenden mit quadrierten euklidischen Abständen
04.03.2010Der Handlungsreisende hat bekanntlich die schwierige Aufgabe eine gegebene Menge von Städten auf einer kürzesten Rundreise zu besuchen. Auf der Konferenz STACS'10 in Nancy berichtet Alexander Wolff über neue Ergebnisse für den Fall, dass die Städte so genannte quadrierte euklidische Abstände haben.
Falls die Städte Punkten in der (euklidischen) Ebene entsprechen und ihre Abstände den "normalen" (euklidischen) Abständen der Punkte entsprechen, so kann man dank eines bahnbrechenden Resultats von Sanjeev Arora die kürzeste Rundreise beliebig gut approximieren. Das Bild rechts zeigt eine sehr einfache Punktemenge und oben (in hellblau) die resultierende kürzeste Rundreise bezüglich euklidischer Abstände.
Bei drahtlosen Ad-hoc-Netzwerken hat man sich intensiv mit quadrierten euklidischen Abständen beschäftigt, da diese den Energieverbrauch in solchen Netzwerken besser wiedergeben. Mit Kollegen aus den Niederlanden hat Alexander Wolff das berühmte Problem des Handlungsreisenden im Hinblick auf diese Abstände untersucht. Im Bild rechts wird durch die orangefarbene Kurve (unten) angegeben, in welcher Reihenfolge die Punkte von einer kürzesten Rundereise durchlaufen werden, wenn man quadrierte euklidische Abstände zugrunde legt.
Das Hauptergebnis des Konferenzbeitrags ist ein effizienter Algorithmus, der für jede Menge von Punkten in der Ebene ein Rundreise berechnet, die höchstens fünfmal so lang ist wie die kürzeste Rundreise (jeweils bezüglich der quadrierten euklidischen Abstände). Der bislang beste Algorithmus konnte nur sechsmal so lange Rundreisen garantieren.
Mehr Information findet sich in den Vortragsfolien und im Konferenzartikel (gemeinsame Arbeit mit Mark de Berg, Fred van Nijnatten, René Sitters und Gerhard Woeginger).
