4511
правок
Миграция данных: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 42: | Строка 42: | ||
'''Представители для больших множеств''' | '''Представители для больших множеств''' | ||
Для множеств размером не менее <math>\beta \;</math> ''непересекающаяся'' коллекция ''множеств представителей'' <math>R_i, i = l, ..., \Delta \;</math> должна удовлетворять следующим свойствам: (1) каждое множество <math>R_i \;</math> должно быть подмножеством <math>D_i \;</math>, (2) <math>|R_i| = | Для множеств размером не менее <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 положим | Для каждого элемента 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] для обобщенной задачи о назначениях. | ||