Algorithmic and Probabilistic Aspects of the Bipartite Traveling Salesman Problem

Baltz, Andreas

(No English summary available.)

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

Quote

Citation style:

Baltz, Andreas: Algorithmic and Probabilistic Aspects of the Bipartite Traveling Salesman Problem.

Rights

Use and reproduction:
No CC License (german copyright law applies)

Export