Dissertation (Metadaten)
Titel:Algorithmic and Probabilistic Aspects of the Bipartite Traveling Salesman Problem
 
Autor:Andreas Baltz
 
URN:NBN:urn:nbn:de:gbv:8-diss-4230
 
Fakultät:Mathematisch-Naturwissenschaftliche Fakultät
DDC Sachgebiet:510 Mathematik
 
Datum der mdl. Prüfung:14.02.2001
 
Referent(in):Prof. Dr. A. Srivastav
Korreferent(en) Korreferentin:Prof. Dr. D. Betten
 
Beschreibung (original):(No English summary available.)
 
(übersetzt):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.
 
Schlagworte:Travelling-salesman-Problem ; Bipartiter Graph ; Bipartite TSP
 
Dokumente:
d423.pdf (2.939 kB)    ZIP generieren   Details >>