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

В статье Кутсупиаса и Пападимитриу предложены и исследованы два варианта уточнения подхода на базе конкурентного анализа, призванные устранить эти претензии. Первым из них является ''диффузная модель соперника'', относящаяся к случаям, в которых о входных данных кое-что известно, а именно – их вероятностное распределение. Учитывая его, оценивается эффективность алгоритма в сравнении его ожидаемой стоимости со стоимостью оптимального алгоритма для входных данных, соответствующих этому распределению.