Онлайн-алгоритмы

Онлайн-алгоритмы должны принимать необратимые решения по мере поступления входных данных, не зная будущих запросов; их качество измеряется конкурентным анализом по сравнению с оптимальным алгоритмом, который видит весь вход заранее.

Definition

Онлайн-алгоритм получает входные данные в виде последовательности запросов и должен немедленно и необратимо отвечать на каждый из них, не видя будущих запросов; его конкурентное отношение — это отношение стоимости алгоритма в худшем случае к стоимости оптимального офлайн-алгоритма, который знает всю последовательность запросов.

Scope

Эта тема охватывает алгоритмы, которые последовательно обрабатывают входные данные и принимают решения до того, как станут известны последующие входные данные, а также структуру конкурентного отношения, используемую для их оценки по сравнению с оптимальным офлайн-противником. Она включает классические задачи — подкачку страниц и кэширование, обновление списков, задачу аренды лыж, задачу k-серверов, а также онлайн-планирование и упаковку в контейнеры — и роль рандомизации в улучшении конкурентных отношений против более слабых противников.

Core questions

• Как оцениваются онлайн-алгоритмы, когда будущее неизвестно?
• Что измеряет конкурентное отношение и что такое офлайн-противник?
• Как классические задачи, такие как подкачка страниц и аренда лыж, иллюстрируют онлайн-компромиссы?
• Как рандомизация может улучшить конкурентоспособность против неосведомленного противника?
• Какие нижние границы ограничивают конкурентоспособность любого онлайн-алгоритма?

Key concepts

• онлайн против офлайн
• конкурентное отношение
• офлайн-противник
• подкачка страниц и кэширование
• обновление списка
• задача аренды лыж
• задача k-серверов
• рандомизированная конкурентоспособность

Key theories

Конкурентный анализ

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

Рандомизация против неосведомленных противников

Рандомизированные онлайн-алгоритмы могут достигать значительно лучших конкурентных отношений, чем любой детерминированный алгоритм, против неосведомленного противника, поскольку противник должен фиксировать входные данные, не зная случайных выборов алгоритма.

Clinical relevance

Онлайн-алгоритмы моделируют решения, которые системы принимают в реальном времени без знания будущего: замена кэша и страниц в операционных системах и ЦП, самоорганизация структур данных, динамическое распределение ресурсов и балансировка нагрузки, а также решения о покупке или аренде в облачных вычислениях. Конкурентный анализ дает гарантии наихудшего случая для таких реактивных систем.

History

Конкурентный анализ был введен Слетором и Тарьяном в 1985 году в их исследовании правил обновления списков и подкачки страниц, переосмыслив оценку онлайн-алгоритмов на основе сравнения с оптимальным офлайн-решением. Эта концепция расширилась благодаря задаче k-серверов и рандомизированным онлайн-алгоритмам в 1990-х годах, что было рассмотрено в монографии Бородина и Эль-Янива 1998 года.

Key figures

• Daniel Sleator
• Robert Tarjan
• Allan Borodin
• Ran El-Yaniv

Seminal works

• sleator1985
• borodin1998
• cormen2009

Frequently asked questions

Что такое конкурентное отношение?

Это отношение стоимости онлайн-алгоритма в худшем случае к стоимости оптимального алгоритма, который видит весь вход заранее. 2-конкурентный алгоритм никогда не стоит более чем в два раза дороже, чем наилучшая возможная офлайн-стоимость для любой входной последовательности.

Почему рандомизация помогает онлайн-алгоритмам?

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