Конспект: онлайн-алгоритмы и конкурентный анализ

Понятия

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

Противник - строит худший вход, зная правило. Незнающий противник - знает правило и вероятности, но не видит выпавших монеток.

Фаза (кеш) - наибольший отрезок запросов с k разными страницами. Инверсия (список) - пара, стоящая в двух списках в разном порядке.

Согласованность - отношение при верном прогнозе; устойчивость - при любом.

Что унести

АРЕНДА ЛЫЖ: прокат 1 в день, покупка B
купить в день B:          2 − 1/B;   лучше без монетки нельзя -
                          сезон кончается в день покупки
B = 10: купить в 1-й - 10, в 5-й - 2,8, в 10-й - 1,9, в 20-й - 2,9
случайный день: вероятность дня i ~ (1 − 1/B)^(B − i)
    1/(1 − (1 − 1/B)^B): при B = 10 - 1,5353;  B → ∞: e/(e − 1) ≈ 1,58

КЕШ НА k СТРАНИЦ
Белади (оптимум): выселить нужную позже всех
LRU, FIFO: k-конкурентны (фазы); детерминированные не лучше k
    круг из k + 1 страниц: промах на каждом запросе
LFU: не конкурентен - старая популярность держит место
трасса из 20 запросов, k = 3: LRU 14, FIFO 13, LFU 11, MIN 10
круг k = 5, 48 запросов: LRU 48, MIN 14
с пометками (случайно из непомеченных): 2Hₖ;  круг k = 5: 24,7
нижняя граница случайных: Hₖ (принцип Яо, случайные запросы
    к k + 1 странице);  2000 запросов, k = 3: отношение 1,83 = H₃

СПИСОК: доступ к позиции i стоит i
«в начало» (MTF): <= 2 · OPT; потенциал - число инверсий
    амортизированно 2v + 1 <= 2i − 1
«с соседом», «по частоте»: не конкурентны
качели 9, 8 × 50: в начало 216, с соседом 1000, неподвижный 950
круг против MTF: 1000 против 550 = 2n/(n + 1)

С ПРОГНОЗОМ (аренда лыж, доверие λ)
прогноз «длинный» - купить в день λB, «короткий» - в день B/λ
согласованность 1 + λ, устойчивость 1 + 1/λ, размен неизбежен
B = 10: λ = 0,5 - 1,4 и 2,9;  λ = 0,2 - 1,1 и 5,9
ошибка прогноза около порога B стоит дороже всего

Ловушки джокера

Сравнил онлайн-алгоритм с другим онлайн-алгоритмом. Мерка - оптимум, знающий будущее.

Раскрыл детерминированное правило противнику. Он построит худший вход по построению.

Выбрал политику кеша по одной трассе. LFU выиграл трассу и проигрывает смену режима во сколько угодно раз.

Ждал от монетки защиты от знающего противника. Против него снова k.

Выбрал «осторожное» правило списка. «С соседом» на качелях платит по n.

Слепо доверился модели. Без устойчивости алгоритм с прогнозом хуже классического.

Мерил модель точностью, а не потерей. Ошибка около порога дороже далёкой.

Проверь себя

Определи конкурентное отношение. Почему «купить в день B» даёт 2 − 1/B и почему лучше без монетки нельзя? Почему LRU k-конкурентен и почему любое детерминированное правило не лучше k? Что делает алгоритм с пометками и откуда нижняя граница Hₖ? Докажи, что «в начало» не хуже двух оптимумов. Что такое согласованность и устойчивость и почему между ними размен?

k серверов: движение в метрике за неизвестной последовательностью запросов. Double coverage на прямой k-конкурентен; ближайший сервер может быть неконкурентным. MTS платит переход плюс обслуживание.

Одноразовый поиск цены: порог √(mM), конкурентное отношение √(M/m). Портфель Ковера сравнивается с постоянными перебалансируемыми долями, а не со всезнающим ежедневным переключением.