Algorithmic and Probabilistic Aspects of the Bipartite Traveling Salesman Problem

Aus der Tourenplanung für Bestückungsroboter stammt folgende Variante des Handlungsreisendenproblems (Traveling Salesman Problem): Die 2n Knoten eines vollständigen Graphen mit nichtnegativen Kantengewichten seien in zwei gleichgroße Klassen eingeteilt. Man finde einen Hamiltonkreis minimalen Gesamtgewichts, der die Klassen in fester Reihenfolge besucht. Die vorliegende Arbeit untersucht insbesondere Instanzen zufälliger Punkte im Einheitsquadrat. Für den Fall unabhängiger gleichverteilter Punkte werden ein optimaler sequentieller Algorithmus, sowie ein paralleler Approximationsalgorithmus mit polylogarithmischer Laufzeit angegeben. Ferner wird der Zusammenhang zwischen dem Wert von Optimallösungen des bipartiten asymmetrischen TSP und seiner Assignmentrelaxierung beleuchtet.

Preview

Rights

Use and reproduction:

No license. The provisions of the German Copyright Act (UrhG) apply.

Please note that individual components of the publication may be subject to other licensing or copyright conditions.

Cite

Citation style:
Could not load citation form.