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.