Heuristiken und exakte Algorithmen für das verallgemeinerte Traveling Salesman Problem
| Talking persons: |
| Dr. Gerold Jäger (Martin-Luther-Universität Halle-Wittenberg) |
| Abstract: |
| Dieser Vortrag ist Teil des Workshops "Algorithmen und Graphen". Wir untersuchen folgendes Minimierungsproblem, das wichtige Anwendungen in der Bioinformatik hat. Finde in einem gerichteten Graphen mit n Knoten eine Tour mit minimalen Kosten, wobei die Kosten jedes Knoten dieser Tour direkt von dem linken und rechten Nachbarn in der Tour abhängen. Dieses Problem kann als Verallgemeinerung des asymmetrischen Traveling Salesman Problems (ATSP) angesehen werden. Einerseits ist es schwerer als das ATSP, da es eine dreidimensionale Kostenfunktion besitzt, andererseits kommen bei beiden Problemen "nur" (n-1)! Touren für die optimale Lösung in Frage. Wir stellen sowohl Heuristiken als auch exakte Algorithmen zu diesem Problem vor, die teils neue Ansätze, teils naheliegende Erweiterungen von ATSP-Algorithmen sind. |
| Times: |
| Monday 14th January 2008, 5.45 pm - 6.15 pm, room 1/346 |
