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

Из теоремы 3 известно, что коэффициент конкурентоспособности любого жадного алгоритма в модели с единичной стоимостью пакетов равен не менее чем 2, если m 3> B. Чемум равна строгая верхняя граница жадных алгоритмов в противоположном случае B»ra?

В доказательстве нижней границы e/(e — 1) в теореме 1 используется соотношение m 2> B, тогда как теорема 5 дает e/(e — 1) в качестве верхней границы для B 2> log m. В работе [ ] приведена нижняя граница 1,366, не зависящая от B и m. Каков оптимальный коэффициент конкурентоспособности для произвольных B и m?

Используя технику редукции общего вида из теоремы 7, можно улучшить коэффициент конкурентоспособности для алгоритмов управления буфером с несколькими очередями в случае достижения улучшенных результатов работы алгоритмов управления буфером с одной очередью. На сегодня лучшими значениями для нижней и верхней границ являются 1 6+ fa 1:43 [ ] и 1,75 [ ], соответственно. Как уменьшить разрыв между этими значениями?