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.

Vorschau

Rechte

Nutzung und Vervielfältigung:

Keine Lizenz. Es gelten die Bestimmungen des deutschen Urheberrechts (UrhG).

Bitte beachten Sie, dass einzelne Bestandteile der Publikation anderweitigen Lizenz- bzw. urheberrechtlichen Bedingungen unterliegen können.

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.