#algorithm #online-algorithm
Вопрос:
Я новичок в области онлайн-алгоритмов. Я вижу, что в большинстве научных работ используется понятие конкурентного соотношения для измерения эффективности предлагаемого онлайн-алгоритма. Можно ли найти такую метрику для любого заданного онлайн-алгоритма?
Комментарии:
1. Нет, хотя многие из этих доказательств основаны на приблизительной дополнительной слабости.