Альтернативные показатели эффективности онлайновых алгоритмов: различия между версиями

Первый результат говорит о том, что для любого соперника <math>D \in \Delta_{\epsilon}</math> существует консервативный соперник <math>\hat{D} \in \Delta_{\epsilon}</math>, такой, что коэффициент конкурентоспособности LRU относительно <math>\hat{D}</math> не меньше, чем коэффициент конкурентоспособности LRU относительно <math>D</math>. Было показано, что для любого консервативного соперника <math>D \in \Delta_{\epsilon}</math> относительно LRU существует консервативный соперник <math>D' \in \Delta_{\epsilon}</math> относительно онлайнового алгоритма A, такой, что коэффициент конкурентоспособности LRU относительно D не превышает коэффициент конкурентоспособности A относительно D0. Иными словами, для любого e LRU имеет оптимальный коэффициент конкурентоспособности R(A€) для диффузной модели соперника. Это основной результат первой части работы [4].

Последний оставшийся вопрос касается значения оптимального коэффициента конкурентоспособности LRU для задачи подкачки. Было показано, что вычислить это значение непросто. Для экстремальных значений e (случаев, когда соперник обладает полным контролем над входными данными и, напротив, практически не обладает им) R(Ai) = k, где k – размер кэша, кроме того, lim€^.o R(A€) = 1. В более поздней работе Янга [ ] удалось оценить R(A€) с коэффициентом аппроксимации, почти равным двум. Для значений " вблизи порога 1/k оптимальный коэффициент составляет @(ln k), для значений ниже этого порога коэффициент быстро стремится к O(1), а выше него – к @{k).