4551
правка
Балансировка нагрузки: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Применение =
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение =) |
||
| Строка 55: | Строка 55: | ||
Самая большая разница возникает в случае несвязанных машин. В отличие от случая постоянных задач, в котором может быть достигнута верхняя граница O(log m) [3], в [2] было показано, что любой алгоритм имеет коэффициент конкурентоспособности <math>\Omega(m / log \; m)</math>. Отметим, что у тривиального алгоритма, который назначает каждое задание машине, имеющей имеет минимальную нагрузку, коэффициент конкурентоспособности не превышает m [3]. | Самая большая разница возникает в случае несвязанных машин. В отличие от случая постоянных задач, в котором может быть достигнута верхняя граница O(log m) [3], в [2] было показано, что любой алгоритм имеет коэффициент конкурентоспособности <math>\Omega(m / log \; m)</math>. Отметим, что у тривиального алгоритма, который назначает каждое задание машине, имеющей имеет минимальную нагрузку, коэффициент конкурентоспособности не превышает m [3]. | ||
= Применение == | == Применение == | ||
Аналогичная модель известна и для задачи упаковки в контейнеры. В этой задаче последовательность состоит из поступлений и убытий элементов размером (0 | Аналогичная модель известна и для задачи упаковки в контейнеры. В этой задаче последовательность состоит из поступлений и убытий элементов размером (0, 1]. Цель заключается в том, чтобы сохранить разбиение имеющихся в данный момент элементов на подмножества (контейнеры), где сумма элементов в каждом подмножестве не превышает 1. Стоимостью является максимальное количество одновременно используемых в любой момент времени контейнеров. Эта задача изучалась в работах [13, 14]. | ||