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

Остается нерешенной задача определения точного коэффициента конкурентоспособности при применении диффузной модели соперника известных алгоритмов (таких как FIFO) для решения задачи подкачки. Известно, что на практике FIFO работает хуже, чем LRU, так что доказательство субоптимального выполнения первого для некоторых значений " обеспечит поддержку этой модели.

Представленный в этой статье открытый подход заключается в рассмотрении так называемой Марковской диффузной модели соперника, которая, как понятно из названия, описывает соперника, генерирующего на выходе последовтальность запросов согласно марковскому процессу.