Wie kommt man auf die Obergrenze (log2(n) + 1) * Optimale Länge im Metrischen Traveling Salesperson Problem?

Question

Aufgabe:

Wie kommt man auf die Obergrenze (log₂(n) + 1) * Optimale Länge im Metrischen Traveling Salesperson Problem?

Mit c(x,y) für die Kantenlänge lautet die Dreiecksungleichung:

 $$c(u, v) <= c(u,w) + c(w, v)$$
Problem/Ansatz:

Wird $$v_j$$ zwischen den Knoten y und z in einem Kreis / einer Tour eingefügt, dann gilt:

$$cost(v_j) = c(y, v_j) + c(v_j, z) - c(y, z)$$

Für $$v_i, v_j$$ gilt:

$$min(cost(v_i), cost(v_j)) <= 2 * cost(v_i, v_j)$$

-> wie kann ich das hier verstehen? Der nächste Knoten, der die niedrigsten Kosten hinsichtlich Kantenlänge verursacht wird ausgewählt und das ist kleiner als die doppelte Kantenlänge von dem gewählten Knoten zu irgendeinen beliebigen anderen Knoten?

Sei $$R* = (w_1, w_2, ... , w_n, w_1)$$ die optimale Tour und $$R = (w_{i1}, w_{i2}, ..., w_{ik}, w_{i1})$$ ein Kreis aus k Knoten mit $$i_j < i_{j + 1}$$. R ist an R* angelehnt. Wegen der Dreiecksungleichung gilt $$c(R) <= c(R*) = OPT$$ (optimale Länge)
-> Was bedeutet R ist an R* angelehnt? Ich nehme an R hat einfach nur weniger Knoten als R*, aber die gleiche Abfolge?
-> Und da ein Umweg über mehr Knoten immer länger ist, muss R < R* sein, außer wenn k = n, dann R = R*?

Dann gibt es eine Menge $$Z ⊂ (w_{i1}, ..., w_{ik})$$  mit $$|Z| = floor(k/2)$$(also abrunden) und
$$cost(Z) <= OPT$$

-> Also gibt es hier eine Menge Z die eine Telmenge von R ist, genauer die Hälfte der Elemente, welche kleiner als die optimale Länge ist
-> ich nehme an, hier wird angenommen, dass Z nicht die gleiche Abfolge wie R hat ? bzw. wie kann man cost(Z) berechnen, wenn die Abfolge noch nicht fest ist

R wird in zwei Mengen geteilt $$M_1 = ((w_{i1}, w_{i2}), ...)$$

und

$$M_2 = ((w_{i2}, w_{i3}), ...)$$, wobei beide floor(k/2) Elemente haben -> haben wir hier jetzt eine Menge von willkürlichen Kanten statt Knoten??

Sei M diejenige für die gilt:$$c(M) <= 1/2 * c(R) <= 1/2 * c(R*)$$

-> wie werden denn hier jetzt die Kanten gebildet? einfach alle aufsummiert ? könnten hier nicht Kombinationen auftauchen, die größer R sind?

Sei Z die Menge der Knoten, die je Kante von M den kleineren Cost-Wert haben, d.h.

$$billigst(u, v) = u, falls cost(u) <= cost(v), sonst v$$
ist $$Z = (billigst(w_{i_j}, w_{i_{j-1}}) | (w_{i_j}, w_{i_{j+1}}) ∈ M )$$
-> ?? warum $$w_{i_{j-1}} und w_{i_{j+1}}$$

-> ich verstehe hier nicht, wie ein Knoten ausgewählt wird
$$cost(Z) = ∑ min(cost(w_{i_j}, w_{i_{j+1}}) <= ∑ 2 * c(w_{i_{j}}, w_{i_{j-1}})$$

$$cost(Z) = 2 * c(M) <= 2 * 1/2 * c(R) <= OPT$$

-> Kanten in M werden iteriert und einer der Knoten gewählt und das ist kleiner als die doppelte Kantenlänge zwischen welchen Knoten??

Mit $$R_1 = R*$$, und $$Z_1$$ wird bestimmt und das für alle $$R_{l+1} = R_l - Z_l$$ für $$l>=1$$ und jedes $$R_l$$ ist an R* angelehnt

$$|R_l| <= n/(2^{l-1})$$, also ist nach $$log(n) + 1$$ Wiederholungen $$U Z_l = {v1, .., v_n}$$

und $$∑ cost(Z_l) <= (log(n) + 1) * OPT$$

-> $$U Z_l$$ steht für die Vereinigung der ganzen Mengen

-> kann ich nicht nachvollziehen, wie groß ist überhaupt ein $$R_1$$ usw?