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

Эта модель применяется к традиционной задаче подкачки для класса распределений <math>\Delta_{\epsilon}</math>. Этот класс содержит все распределения вероятностей, такие, что для заданной последовательности запросов и страницы p вероятность того, что p является следующей запрошенной страницей, не выше e. Было показано, что хорошо известный онлайновый алгоритм LRU достигает оптимального коэффициента конкурентоспособности R(A€) для всех e, иначе говоря, что он является оптимальным по отношению к любому сопернику, использующему распределение этого класса.

Доказательство этого утверждения основывается на понятии рабочей функции, введенном в [ ], которе используется в качестве инструмента отслеживания поведения оптимального оффлайнового алгоритма и оценки оптимальной стоимости последовательности запросов, а также тех не параметров для консервативных соперников, которые назначают более высокие вероятности недавно запрошенным страницам. Этот тип соперника согласуется с локальностью ссылок – понятием, которое всегда было связано с алгоритмами подкачки и конкурентным анализом (хотя в работе [1] другое семейство распределений было предложено и проанализировано в рамках данной структуры, точнее отражающей это понятие).

Первый результат говорит о том, что для любого соперника D 2 A€ существует консервативный соперник D € A€, такой, что коэффициент конкурентоспособности LRU относительно с D не меньше, чем коэффициент конкурентоспособности LRU относительно D. Было показано, что для любого консервативного соперника D 2 A€ относительно LRU существует консервативный соперник D0 2 A€ относительно онлайнового алгоритма A, такой, что коэффициент конкурентоспособности LRU относительно D не превышает коэффициент конкурентоспособности A относительно D0. Иными словами, для любого e LRU имеет оптимальный коэффициент конкурентоспособности R(A€) для диффузной модели соперника. Это основной результат первой части работы [4].