Обмен пакетами при помощи одного буфера: различия между версиями

'''Теорема 1 [3]. Для f$ = 4 конкурентоспособности алгоритма MPG составляет 1,75.'''

Для доказательства вначале было показано, что для анализа эффективности работы MPG достаточно рассмотреть только экземпляры входных данных, у которых стоимость каждого пакета равна либо 0, либо f$l для некоторого i > 0, но при этом допускается разрешение ситуаций с ничьей при помощи противника.

Затем авторы определили структуру интервалов для экземпляров входных данных. Интервал I имеет тип i, если на каждом шаге t 2 экземпляр IMPG выдает пакет стоимостью не меньше ft', при этом I является максимальным интервалом с таким свойством.

Ii – это набор максимальных интервалов типа i, а I – объединение всех коллекций Ii. Оно является мультимножеством, поскольку интервал типа i также может входить в интервал одного или нескольких типов j < i.

Этот подход порождает структуру интервалов, представляющую собой естественную последовательность упорядоченных корневых деревьев: корнем каждого дерева является интервал из %, а потомками каждого интервала I 2 Ii являются все максимальные интервалы типа i + 1, содержащиеся в I. Эти потомки упорядочены слева направо по времени, также как и сами деревья. Интервалы типа i (и представляющие их вершины) различаются по тому, был или не был на этом интервале исключен пакет стоимостью не менее f$l.

В завершение доказательства авторы показали, что для каждой структуры интервалов T коэффициент конкурентоспособности алгоритма MPG на экземплярах со структурой интервалов T может быть ограничен решением линейной программы, индексированной T. Наконец, было показано, что для любого T и любого /3 > 4 решение этой программы не превышает 2 — 1/f$.