4670
правок
Обмен пакетами при переключении между несколькими очередями: различия между версиями
Материал из WEGA
Обмен пакетами при переключении между несколькими очередями (посмотреть исходный код)
Версия от 11:33, 11 января 2020
, 11 января 2020→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 50: | Строка 50: | ||
'''Теорема 5 [3]. Алгоритм <math>E^{M^{\hat{EP'}}}</math> (который не будет здесь описываться подробно), основанный на алгоритме уровня воды и использующий частичное соответствие в графе, | '''Теорема 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>.''' | ||
| Строка 58: | Строка 58: | ||
'''Теорема 7 (Обобщение техники [9]). Если существует рандомизированный c-конкурентный алгоритм A для B = 1, существует рандомизированный c-конкурентный алгоритм <math>\tilde{A}</math> для всех B.''' | '''Теорема 7 (Обобщение техники [9]). Если существует рандомизированный c-конкурентный алгоритм A для B = 1, то существует рандомизированный c-конкурентный алгоритм <math>\tilde{A}</math> для всех B.''' | ||
'''Алгоритм | '''Алгоритм RS (случайный план)''' | ||
1. Алгоритм использует m вспомогательных очередей <math>Q_1, ..., Q_m</math> размерами <math>B_1, ..., B_m</math> (допускаются различные размеры буфера для разных портов), соответственно. Эти очереди содержат вещественные числа из интервала (0, 1), в свою очередь, каждое число помечено как маркированное или немаркированное. Изначально все очереди пусты. | 1. Алгоритм использует m вспомогательных очередей <math>Q_1, ..., Q_m</math> размерами <math>B_1, ..., B_m</math> (допускаются различные размеры буфера для разных портов), соответственно. Эти очереди содержат вещественные числа из интервала (0, 1), в свою очередь, каждое число помечено как маркированное или немаркированное. Изначально все очереди пусты. | ||
