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

Для множеств размером не менее <math>\beta \;</math> ''непересекающаяся'' коллекция ''множеств представителей'' <math>R_i, i = l, ..., \Delta \;</math> должна удовлетворять следующим свойствам: (1) каждое множество <math>R_i \;</math> должно быть подмножеством <math>D_i \;</math>, (2) <math>|R_i| = \lfloor| D_i | / \beta \rfloor \;</math>. Множества представителей могут быть найдены при помощи алгоритма вычисления потока в сети.

Для каждого элемента i положим <math>\gamma_i = | D_i | \; mod \; k</math>. Необходимо вычислить ''вторичного представителя'' <math>r_i в D_i \;</math> для элементов с <math>\gamma_i \ne 0 \;</math>. Диск j может быть вторичным представителем <math>r_i \;</math> для нескольких элементов, если <math>\sum_{i \in I_j} \gamma_i \le 2 \beta + 1 \;</math>, где <math>I_j \;</math> – множество элементов, для которых j является вторичным представителем. Это можно сделать при помощи алгоритма Шмойса-Тардош [17] для обобщенной задачи о назначениях.