4.) Beweis der 2erKompetitivität des MF-Algorithmus:

Sei:

OPT = optimaler offline Algorithmus
MF = MF-Regel (move-to-front)

L = eine Liste von Elementen
s = Zugriffsfolge mit Länge m
L_OPT = Liste durch OPT modifiziert
L_MF = Liste durch MF modifiziert
C_OPT (i) = Kosten/Aufwand nach der i-ten Operation nach OPT
C_MF (i) = Kosten/Aufwand nach der i-ten Operation nach MF
K = Kontostand, der sich aus den Unterschieden der beiden Listen (L_A und L_MF) ergibt. K = bal (L_A,L_MF).
K_i = Kontostand bevor auf das der (i+1)-ten Element aus s zugegriffen wird.
o.B.d.A. gilt anfangs L_OPT = L_MF und somit K(0) = 0;
x = immer das Element auf das zugegriffen werden soll.

(0 <= i <= m-1)
k = Anzahl der Elemente die, in L_MF und L_OPT, x vorausgehen (weiter vorne in der Liste stehen).
l = Anzahl der Elemente die in L_MF vor x und in L_OPT hinter x stehen.
= > C_OPT (i) >= k +1

Da kein Element sowohl zu l als auch zu k beitragen kann (ansonsten müsste es in L_OPT doppelt vorkommen),
und da sowohl die Elemente die zu l als auch zu k beitragen vor x stehen, folgt:

=> C_MF (i) = k + l + 1
(Es stehen k + l Elemente vor x in L_MF => Die Kosten beim Zugriff von MF sind k + l +1.)

Wenn MF auf x zugreift und x und an den Listenanfang verschiebt, werden l Inversionen zerstört und maximal k neue "erzeugt".
(Die Anzahl der Inversionen die vor einem Zugriff existieren, wird also um l gesenkt und maximal um k gesteigert.
D.h. also: Die "neue" Anzahl an Inversionen kann maximal die "alte" Anzahl an Inversionen - l + k sein.)

=> K_i+1 <= K_i - l + k

<=> K_i+1 - K_i <= - l + k

<=> C_MF (i+1) + K_i+1 - K_i <= C_MF (i+1) + k - l (P : = diese Ungleichung)
( C_MF (i+1) + K_i+1 - K_i = : p)

da C_MF (i+1) + k - l = k + l +1 + k -l = 2* k +1
<=> C_MF (i+1) + K_i+1 - K_i <= 2* C_OPT (i+1) -1

folgt für s:

[

CMF (i+1) ] + K(m) - K(0)

<=

[

2* COPT (i+1)] - m

 

bzw.:(Teleskop-Summe)

C_MF(s) <= 2* C_OPT (s) - m - K(m) + K(0)

=> MF ist 2 kompetitiv.

weiterführende Anmerkung:
Jeder kostenpflichtige Austausch, den OPT beim Zugriff auf ein Element tätigt, kann p um 1 erhöhen; jedoch erhöht OPT so auch seine Kosten um 1.
=> Ungleichung P bleibt erhalten, der Beweis gilt weiterhin.

Die obige Beweisführung gilt auch noch, wenn es möglich ist, Elemente zu löschen und/oder einzufügen.
Beim Einfügen eines Elementes entstehen sowohl für OPT als auch für MF Kosten in der Höhe von n +1. Hierbei ist n die Anzahl der Elemente vor der "Einfügungsposition" in der Liste.
Und es werden maximal n neue Inversionen "erzeugt".
Beim Löschen werden l Inversionen "zerstört" und keine neuen Inversionen "erzeugt".
Ein vergleichbarer Beweis zeigt das MF höchstens doppelt so "schlecht" ist wie jeder andere Algorithmus zur Anordnung von Listen.