Миграция данных: различия между версиями

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].

Заметим, что общее количество раундов, необходимых для выполнения вышеописанного алгоритма, не превышает 2M + 2.5a + 5f$ - 3. Поскольку a, f$ и M являются нижними границами оптимального количества раундов, этот алгоритм дает 9,5-аппроксимацию.