4431
правка
Миграция данных: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 28: | Строка 28: | ||
2. '''Максимальное количество элементов, источником или назначением которых может быть диск <math>(\alpha \;</math>):''' Для каждого элемента i по меньшей мере один диск в <math>S_i \;</math> должен быть использован в качестве источника элемента, этот диск называется ''первичным источником''. Уникальный первичный источник <math>s_i \in S_i \;</math> для каждого элемента i, минимизирующего значение <math>\alpha = max_{j = 1, ..., N} (| \{ i | j = s_i \} |) \;</math>, может быть найден при помощи алгоритма вычисления потока в сети. Отметим, что <math>\alpha \ge \beta \;</math>; <math>\alpha \;</math> также является нижней границей оптимального решения. | 2. '''Максимальное количество элементов, источником или назначением которых может быть диск <math>(\alpha \;</math>):''' Для каждого элемента i по меньшей мере один диск в <math>S_i \;</math> должен быть использован в качестве источника элемента, этот диск называется ''первичным источником''. Уникальный первичный источник <math>s_i \in S_i \;</math> для каждого элемента i, минимизирующего значение <math>\alpha = max_{j = 1, ..., N} (| \{ i | j = s_i \} |) \;</math>, может быть найден при помощи алгоритма вычисления потока в сети. Отметим, что <math>\alpha \ge \beta \;</math>; <math>\alpha \;</math> также является нижней границей оптимального решения. | ||
3. '''Минимальное время, необходимое для клонирования (M):''' Пусть диск j делает копию элемента i в k-м раунде. В конце m-го раунда количество копий, которые могут быть созданы из этой копии, не превышает <math>2^{m - k} \;</math>, поскольку в каждом раунде количество копий может только удваиваться. Отметим также, что каждый диск может в одном раунде сделать копию только одного элемента. Поскольку нужно создать не менее | | 3. '''Минимальное время, необходимое для клонирования (M):''' Пусть диск j делает копию элемента i в k-м раунде. В конце m-го раунда количество копий, которые могут быть созданы из этой копии, не превышает <math>2^{m - k} \;</math>, поскольку в каждом раунде количество копий может только удваиваться. Отметим также, что каждый диск может в одном раунде сделать копию только одного элемента. Поскольку нужно создать не менее <math>|D_i| \;</math> копий элемента i, минимальное значение m, удовлетворяющее следующей линейной программе, задает нижнюю границу оптимального решения: | ||
'''L(m):''' | |||
| Строка 41: | Строка 37: | ||
9,5-аппроксимацию можно получить следующим образом. | 9,5-аппроксимацию можно получить следующим образом. | ||
Алгоритм вначале вычисляет множества представителей для каждого элемента и отправляет элемент в множество, которое, в свою очередь, пересылает элемент в оставшееся множество. Множества представителей вычисляются по-разному в зависимости от размера | Алгоритм вначале вычисляет множества представителей для каждого элемента и отправляет элемент в множество, которое, в свою очередь, пересылает элемент в оставшееся множество. Множества представителей вычисляются по-разному в зависимости от размера <math>D_i \;</math>. | ||
'''Представители для больших множеств''' | '''Представители для больших множеств''' | ||
Для множеств размером не менее | Для множеств размером не менее <math>\beta \;</math> ''непересекающаяся'' коллекция ''множеств представителей'' <math>R_i, i = l, ..., \Delta \;</math> должна удовлетворять следующим свойствам: (1) каждое множество <math>R_i \;</math> должно быть подмножеством <math>D_i \;</math>, (2) <math>|R_i| = || D_i | / \beta \;</math>. Множества представителей могут быть найдены при помощи алгоритма вычисления потока в сети. | ||