4551
правка
Миграция данных: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
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. Максимальное количество элементов, источником или назначением которых может быть диск ( | 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-го раунда количество копий, которые могут быть созданы из этой копии, не превышает | 3. '''Минимальное время, необходимое для клонирования (M):''' Пусть диск j делает копию элемента i в k-м раунде. В конце m-го раунда количество копий, которые могут быть созданы из этой копии, не превышает <math>2^{m - k} \;</math>, поскольку в каждом раунде количество копий может только удваиваться. Отметим также, что каждый диск может в одном раунде сделать копию только одного элемента. Поскольку нужно создать не менее |D| копий элемента i, минимальное значение m, удовлетворяющее следующей линейной программе, задает нижнюю границу оптимального решения: L(m): | ||
(1) (2) (3) | (1) (2) (3) | ||
m | m | ||
