4551
правка
Миграция данных: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
'''Нотация и нижние границы''' | '''Нотация и нижние границы''' | ||
1. '''Максимальная полустепень захода ( <math>\beta \;</math>):''' Пусть <math>\beta_j \;</math> – количество элементов данных, которые собирается получить диск j. Иными словами, <math>\beta_j = | \{i | j \in D_i\} |</math>. Тогда <math>\beta = max_j \beta_j \;</math> является нижней границей оптимума, поскольку диск может получить только один элемент данных в одном раунде. | 1. '''Максимальная полустепень захода (<math>\beta \;</math>):''' Пусть <math>\beta_j \;</math> – количество элементов данных, которые собирается получить диск j. Иными словами, <math>\beta_j = | \{i | j \in D_i\} |</math>. Тогда <math>\beta = max_j \beta_j \;</math> является нижней границей оптимума, поскольку диск может получить только один элемент данных в одном раунде. | ||
2. '''Максимальное количество элементов, источником или назначением которых может быть диск <math>(\alpha \;</math>):''' Для каждого элемента i по меньшей мере один диск в <math>S_i \;</math> должен быть использован в качестве источника элемента, этот диск называется ''первичным источником''. Уникальный первичный источник <math>s_i \in S_i \;</math> для каждого элемента i, | 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 \} | + \beta_j) \;</math>, может быть найден при помощи алгоритма вычисления потока в сети. Отметим, что <math>\alpha \ge \beta \;</math>; <math>\alpha \;</math> также является нижней границей оптимального решения. | ||
3. '''Минимальное время, необходимое для клонирования (M):''' Пусть диск j делает копию элемента i в k-м раунде. В конце m-го раунда количество копий, которые могут быть созданы из этой копии, не превышает <math>2^{m - k} \;</math>, поскольку в каждом раунде количество копий может только удваиваться. Отметим также, что каждый диск может в одном раунде сделать копию только одного элемента. Поскольку нужно создать не менее <math>|D_i| \;</math> копий элемента i, минимальное значение m, удовлетворяющее следующей линейной программе, задает нижнюю границу оптимального решения: | 3. '''Минимальное время, необходимое для клонирования (M):''' Пусть диск j делает копию элемента i в k-м раунде. В конце m-го раунда количество копий, которые могут быть созданы из этой копии, не превышает <math>2^{m - k} \;</math>, поскольку в каждом раунде количество копий может только удваиваться. Отметим также, что каждый диск может в одном раунде сделать копию только одного элемента. Поскольку нужно создать не менее <math>|D_i| \;</math> копий элемента i, минимальное значение m, удовлетворяющее следующей линейной программе, задает нижнюю границу оптимального решения: | ||
| Строка 40: | Строка 40: | ||
9,5-аппроксимацию можно получить следующим образом. | 9,5-аппроксимацию можно получить следующим образом. | ||
Алгоритм вначале вычисляет множества представителей для каждого элемента и отправляет элемент в | Алгоритм вначале вычисляет множества представителей для каждого элемента и отправляет элемент в множества представителей, которые, в свою очередь, пересылают элемент в оставшееся множество. Множества представителей вычисляются по-разному в зависимости от размера <math>D_i \;</math>. | ||
