Direkt zum Inhalt

Lexikon der Mathematik: Assignment-Relaxation

die Relaxation des Traveling-Salesman-Problems, bei der die Menge der Orte nicht notwendigerweise durch eine Rundreise, sondern durch eine beliebige Anzahl von disjunkten Rundreisen zwischen jeweils mindestens zwei Orten überdeckt werden soll.

Dieses neue Problem läßt sich in polynomieller Zeit lösen. Die Kosten einer optimalen Lösung der Assignment-Relaxation des TSP bilden eine untere Schranke für die Kosten einer optimalen Rundreise. Damit kann die Assignment-Relaxation für das Modul der Berechnung einer unteren Schranke in Branch-and-Bound Algorithmen für das TSP benutzt werden.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos