4551
правка
Миграция данных: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 59: | Строка 59: | ||
2. '''Миграция в <math>r_i \;</math>:''' элемент i отправляется из первичного источника <math>s_i \;</math> в <math>r_i \;</math>. Эту миграцию можно выполнить за <math>1,5 \alpha \;</math> раундов при помощи раскраски ребер [16]. | 2. '''Миграция в <math>r_i \;</math>:''' элемент i отправляется из первичного источника <math>s_i \;</math> в <math>r_i \;</math>. Эту миграцию можно выполнить за <math>1,5 \alpha \;</math> раундов при помощи раскраски ребер [16]. | ||
3. '''Миграция на оставшиеся диски:''' Теперь можно создать граф переноса из представителей на оставшиеся диски следующим образом. Для каждого элемента i добавьте ориентированные ребра от дисков в | 3. '''Миграция на оставшиеся диски:''' Теперь можно создать граф переноса из представителей на оставшиеся диски следующим образом. Для каждого элемента i добавьте ориентированные ребра от дисков в <math>R_i \;</math> к <math>(\beta - 1) \lfloor \frac{|D_i|}{\beta} \rfloor \;</math> дисков в <math>D_i \backslash R_i \;</math>, такие, что полустепень выхода каждой вершины в <math>R_i \;</math> не превышает <math>\beta - 1 \;</math>, а полустепень входа каждой вершины в <math>D_i \backslash \R_i \;</math> из <math>R_i \;</math> равна 1. Также добавляется ориентированное ребро от вторичного представителя <math>r_i \;</math> элемента i к оставшимся дискам в <math>D_i \;</math>, не имеющим входящих ребер из <math>R_i \;</math>. Было показано, что максимальная степень графа переносов не превышает <math>4 \beta - 5 \;</math>, а кратность равна <math>\beta + 2 \;</math>. Следовательно, миграцию из графа переносов можно выполнить за 5f$ - 3 раундов при помощи алгоритма раскраски ребер мультиграфа [18]. | ||