4430
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
Строка 128: | Строка 128: | ||
Техника редукции общего вида позволяет ограничиться исследованием задач об управлении буфером с одной очередью. Ее можно применить к 1,75-конкурентному алгоритму PG, предложенному Бансалом и коллегами [ ], который обеспечивает лучшее на настоящий момент соотношение и является основой алгоритма | Техника редукции общего вида позволяет ограничиться исследованием задач об управлении буфером с одной очередью. Ее можно применить к 1,75-конкурентному алгоритму PG, предложенному Бансалом и коллегами [7], который обеспечивает лучшее на настоящий момент соотношение и является основой алгоритма <math>GS^{PG}</math>, 3,5-конкурентный для буферов с несколькими очередями (при этом 3,5 все же выше 3 – коэффициента конкурентоспособности алгоритма TLH). В рамках модели с вытеснением для двух вариантов стоимости Лоткер и Пэтт-Шамир [8] представили ''алгоритм разметки и сброса'' (mark&flush algorithm) mf, являющийся 1,3-конкурентным для буферов с одной очередью, и технику редукции общего вида, которая преобразует его в 2,60-конкурентный алгоритм <math>GS^{mf}</math> для буферов с несколькими очередями. | ||
Для общей модели без вытеснения Энделман и др. [2] представили политику для случая с одной очередью под названием «карусель с экспоненциальными интервалами» (Exponential-Interval Round-Robin, EIRR), являющуюся ( | Для общей модели без вытеснения Энделман и др. [2] представили политику для случая с одной очередью под названием «карусель с экспоненциальными интервалами» (Exponential-Interval Round-Robin, EIRR), являющуюся <math>(e \left \lceil \ln \alpha \right \rceil)</math>-конкурентной, и доказали более низкую границу, составляющую <math>\Theta(log \; a)</math>. Для случая буфера с несколькими очередями техника редукции общего вида позволяет получить <math>(e \left \lceil \ln \alpha \right \rceil)</math>-конкурентный алгоритм без вытеснения. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Из теоремы 3 известно, что коэффициент конкурентоспособности любого жадного алгоритма в модели с единичной стоимостью пакетов равен не менее чем 2, если m 3> B. Чемум равна строгая верхняя граница жадных алгоритмов в противоположном случае B»ra? | Из теоремы 3 известно, что коэффициент конкурентоспособности любого жадного алгоритма в модели с единичной стоимостью пакетов равен не менее чем 2, если m 3> B. Чемум равна строгая верхняя граница жадных алгоритмов в противоположном случае B»ra? |
правок