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

В процессе конкурентного анализа эффективность онлайнового алгоритма сравнивается с эффективностью его всемогущего соперника на входных данных, относящихся к наихудшему случаю. Коэффициент конкурентоспособности алгоритма A определяется как наихудшее возможное отношение <math>R_A = max_x \frac{A(x)}{opt(x)}</math>, где x пробегает все возможные входные данные задачи, а A(x) и opt(x) представляют собой стоимость решений, полученных алгоритмом A и оптимальным оффлайновым алгоритмом для входного значения x, соответственно. [''Все задачи в данной статье предполагаются онлайновыми задачами минимизации, следовательно, цель заключается в минимизации затрат. Все представленные здесь результаты действительны и для онлайновых задач максимизации с соответствующими корректировками в определениях'']. Это понятие может быть расширено для определения коэффициента конкурентоспособности задачи как минимального коэффициента конкурентоспособности алгоритма ее решения, а именно <math>R = min_A R_A = min_A max_x \frac{A(x)}{opt(x)}.</math>

Доказательство этого утверждения основывается на понятии ''рабочей функции'', введенном в [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.

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