Альтернативные показатели эффективности онлайновых алгоритмов

Постановка задачи

Несмотря на то, что онлайновые алгоритмы изучались более тридцати лет, явное введение сравнительного (конкурентного) анализа в основополагающих статьях Слейтора и Тарьяна [8] и Манасса, Макгиоха и Слейтора [ ] привело к взрывному росту количества исследований этого класса задач и алгоритмов, и с тех пор оба понятия (онлайновые алгоритмы и конкурентный анализ) остаются тесно связанными друг с другом. Онако уже на раннем этапе этих исследований возникли вопросы к реалистичности и практичности модели, связанные главным образом с ее пессимизмом. Эта характеристика в некоторых случаях сказывается на способности модели к различению хороших и плохих алгоритмов. В статье 1994 года «За пределами конкурентного анализа» [ ] Кутсупиас и Пападимитриу предложили и исследовали два альтернативных показателя эффективности онлайновых алгоритмов, тесно связанные с конкурентным анализом и при этом лишенные вышеупомянутых слабостей. Окончательная версия этой работы вышла в 2000 году [4].

В процессе конкурентного анализа эффективность онлайнового алгоритма сравнивается с эффективностью его вечного противника на входных данных, относящихся к наихудшему случаю. Коэффициент конкурентоспособности алгоритма A определяется как наихудшее возможное отношение R = max A(x) opt(x) ; где x пробегает все возможные входные данные задачи, а A(x) и opt(x) представляют собой стоимость решений, полученных алгоритмом A, и оптимальный оффлайновый алгоритм для входного значения x1, соответственно. Это понятие может быть расширено для определения коэффициента конкурентности задачи как минимального коэффициента конкурентности алгоритма ее решения, а именно R = min RA = min max A Ax opt(x)