4430
правок
Обмен пакетами при переключении между несколькими очередями: различия между версиями
Перейти к навигации
Перейти к поиску
м
Обмен пакетами при переключении между несколькими очередями (посмотреть исходный код)
Версия от 23:26, 8 января 2020
, 8 января 2020→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 50: | Строка 50: | ||
'''Теорема 5 [3]. Алгоритм <math>E^{M^{\hat{EP'}}}</math> (который не будет здесь описываться подробно), основанный на алгоритме уровня воды и использующий частичное соответствие в графе, построенном в онлайновом режиме, имеет коэффициент конкурентоспособности <math>e/(e - 1) (1 + (\lfloor H_m + 1 \rfloor)/B)</math>, где <math>H_m</math> обозначает m-е гармоническое число. Таким образом, | '''Теорема 5 [3]. Алгоритм <math>E^{M^{\hat{EP'}}}</math> (который не будет здесь описываться подробно), основанный на алгоритме уровня воды и использующий частичное соответствие в графе, построенном в онлайновом режиме, имеет коэффициент конкурентоспособности <math>e/(e - 1) (1 + (\lfloor H_m + 1 \rfloor)/B)</math>, где <math>H_m</math> обозначает m-е гармоническое число. Таким образом, <math>E^{M^{\hat{EP'}}}</math> является асимптотически <math>\frac{e}{e - 1}</math>-конкурентным для <math>B \gg log \; m</math>.''' | ||
'''Рандомизированные алгоритмы''' | '''Рандомизированные алгоритмы''' | ||
'''Теорема 6 [1]. Коэффициент конкурентоспособности каждого рандомизированного онлайнового алгоритма не может быть меньше <math>\varrho = 1,4659</math> для любого размера буфера B (<math>\varrho = 1 + \frac{1}{\alpha + 1}</math>, где <math>\alpha</math> – единственный положительный корень уравнения <math>e^{\alpha} = \alpha + 2</math>).''' | |||
'''Теорема 7 (Обобщение техники [9]). Если существует рандомизированный c-конкурентный алгоритм A для B = 1, существует рандомизированный c-конкурентный алгоритм <math>\tilde{A}</math> для всех B.''' | |||
Теорема 7 (Обобщение техники [ ]). Если существует рандомизированный c-конкурентный алгоритм A для B = 1, существует рандомизированный c-конкурентный алгоритм A для всех B. | |||