4551
правка
Миграция данных: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 57: | Строка 57: | ||
1. '''Миграция в <math>R_i \;</math>''': каждый элемент данных вначале отправляется в множество <math>R_i \;</math>. Преобразуя дробное решение, приведенное в L(M), можно найти график миграции из <math>s_i \;</math> в <math>R_i \;</math>, требующий не более <math>2M + \alpha \;</math> раундов. | 1. '''Миграция в <math>R_i \;</math>''': каждый элемент данных вначале отправляется в множество <math>R_i \;</math>. Преобразуя дробное решение, приведенное в L(M), можно найти график миграции из <math>s_i \;</math> в <math>R_i \;</math>, требующий не более <math>2M + \alpha \;</math> раундов. | ||
2. Миграция в | 2. '''Миграция в <math>r_i \;</math>:''' элемент i отправляется из первичного источника <math>s_i \;</math> в <math>r_i \;</math>. Эту миграцию можно выполнить за <math>1,5 \alpha \;</math> раундов при помощи раскраски ребер [16]. | ||
3. Миграция на оставшиеся диски: Теперь можно создать граф переноса из представителей на оставшиеся диски следующим образом. Для каждого элемента i добавьте ориентированные ребра от дисков в Ri к ф - 1) |_^J дискам в D \ Rt, такие, что полустепень выхода каждой вершины в Ri не превышает f$ — 1, а полустепень входа каждой вершины в Д \ Ri из Ri равна 1. Также добавляется ориентированное ребро от вторичного представителя ri элемента i к оставшимся дискам в D, не имеющим входящих ребер из Ri. Было показано, что максимальная степень графа переносов не превышает 4/3 – 5, а кратность равна f$ + 2. Следовательно, миграцию из графа переносов можно выполнить за 5f$ - 3 раундов при помощи алгоритма раскраски ребер мультиграфа [18]. | 3. '''Миграция на оставшиеся диски:''' Теперь можно создать граф переноса из представителей на оставшиеся диски следующим образом. Для каждого элемента i добавьте ориентированные ребра от дисков в Ri к ф - 1) |_^J дискам в D \ Rt, такие, что полустепень выхода каждой вершины в Ri не превышает f$ — 1, а полустепень входа каждой вершины в Д \ Ri из Ri равна 1. Также добавляется ориентированное ребро от вторичного представителя ri элемента i к оставшимся дискам в D, не имеющим входящих ребер из Ri. Было показано, что максимальная степень графа переносов не превышает 4/3 – 5, а кратность равна f$ + 2. Следовательно, миграцию из графа переносов можно выполнить за 5f$ - 3 раундов при помощи алгоритма раскраски ребер мультиграфа [18]. | ||