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

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

Первый результат говорит о том, что для любого соперника <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 относительно D'. Иными словами, для любого <math>\epsilon</math> LRU имеет оптимальный коэффициент конкурентоспособности <math>R(\Delta_{\epsilon})</math> для диффузной модели соперника. Это основной результат первой части работы [4].

Наконец, было показано, что для конкретной метрической системы задач эффективность просмотра вперед строго меньше вышеуказанной: для задачи подкачки сравнительное отношение составляет в точности min{''l + 1, k''}, то есть преимущество использования просмотра представляет собой минимальное из значений размера кэша и размера окна просмотра вперед плюс 1.

* [[Онлайн-алгоритм интервальной раскраски]]