Travelling Salesman Problem

Definition:
Ein Hamiltonkreis in einem Graphen ist ein Kreis, der jeden Knoten genau einmal durchläuft.

Definition:
Das Travelling Salesman Problem minTSP sucht den minimalen Hamiltonkreis in einem Graphen.

Theorem: [Gonzalez]
Wenn minTSP $\in AXP$, dann $P=NP$.
Folge: minTSP $\in NPO$

Approximationsalgorithmus:
Berechne minimalen Spannbaum (in polynomialer Zeit) und laufe die Knoten in Tiefensuche ab. Diese Lösung $A(I)$ ist höchstens doppelt so schlecht wie $OPT(I)$.