Die Christofides-Heuristik ist ein Algorithmus, der zur Approximation von metrischen Problemen des Handlungsreisenden dient. Sie ist die zur Zeit beste Heuristik für solche Probleme mit einer festen Gütegarantie. Formal geht man ähnlich wie bei der Minimum-Spanning-Tree-Heuristik vor: == Gütegarantie == Es lässt sich zeigen, dass die Christof...