Жадные алгоритмы аппроксимации: различия между версиями
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 35 промежуточных версий этого же участника) | |||
| Строка 8: | Строка 8: | ||
Жадный алгоритм A: | '''Жадный алгоритм A:''' | ||
<math>C \leftarrow \empty</math> | |||
'''while''' <math>f(C) > 2 ;\ </math> '''do''' | |||
выбрать вершину x так, чтобы максимизировать <math>f(C) - f(C \cup \{ x \} )</math> и <math>C \leftarrow C \cup \{ x \}</math>; вывести C. | |||
Здесь f определяется как f(C) = p(C) + q(C), где p(C) – количество связных компонент подграфа, порожденного C, а q(C) – количество связных компонент подграфа с множеством вершин V и множеством дуг <math>\{ (u, v) \in E | u \in C </math> или <math> v \in C \}</math>. Функция f обладает важным свойством: C является связным доминирующим множеством в том и только том случае, если f(C) = 2. | |||
Проведем некоторый анализ вышеприведенного жадного алгоритма: Пусть | |||
Если C является связным доминирующим множеством, то p(C) = q(C) = 1 и, следовательно, f(C) = 2. Напротив, предположим, что <math>f(C \cup \{ x \}) = 2</math>. Поскольку <math>p(C) \ge 1 \;</math> и <math>q(C) \ge 1 \;</math>, должно иметь место p(C) = q(C) = 1, из чего следует, что C является связным доминирующим множеством. Функция f обладает еще одним свойством на графе G, имеющем не менее трех вершин: если f(C) > 2, то существует <math>x \in V \;</math>, такое, что <math>f(C) - f(C \cup \{ x \} ) > 0</math>. Фактически, для <math>C \ne \empty \;</math>, поскольку G является связным графом, имеющим не менее трех вершин, должна существовать вершина x со степенью не ниже двух, и для такой вершины x выполняется <math>f(C \cup \{ x \}) < f(C)</math>. Для случая <math>C \ne \empty \;</math> рассмотрим связную компоненту подграфа, порожденного C. Обозначим как B его множество вершин, являющееся подмножеством C. Для каждой вершины y, смежной с B, в случае, если y смежна с вершиной, не смежной с B и не принадлежащей к C, то <math>p(C \cup \{ y \} ) < p(C)</math> и <math>q(C \cup \{ y \} ) \le q(C)</math>; если вершина y смежна с вершиной из множества C — B, то <math>p(C \cup \{ y \} ) \le p(C)</math> и <math>q(C \cup \{ y \} ) < q(C)</math>. | |||
Проведем некоторый анализ вышеприведенного жадного алгоритма: Пусть <math>x_1, ..., x_g \;</math> – вершины, выбранные жадным алгоритмом в порядке их появления в алгоритме. Введем обозначение <math>C_i = \{ x_1, ... , x_i \} \;</math>. Пусть <math>C^* = \{ y_1, ..., y_{opt} \} \; </math> – минимальное связное доминирующее множество. Поскольку добавление <math>C^* \; </math> к <math>C_i \;</math> уменьшит значение гармонической функции с <math>f(C_i) \;</math> до 2, значение f, уменьшенной на вершину из <math>C^* \;</math>, будет в среднем составлять <math>(f(C_i) - 2)/opt \;</math>. Но, согласно жадному правилу выбора <math>x_i + 1 \;</math>, должно иметь место соотношение <math>f(C_i) - f(C_{i + 1}) \ge \frac{f(C_i) - 2}{opt}</math>. | |||
Следовательно, <math>f(C_{i + 1}) - 2 \le (f(C_i) - 2) (1 - \frac{1}{opt}) \le (f( \empty ) - 2) (1 - \frac{1}{opt})^{i + 1} = (n - 2) (1 - \frac{1}{opt})^{i + 1}</math>, | |||
Следовательно, | |||
1 | |||
opt | где <math>n = |V| \;</math>. Заметим, что <math>1 - 1/ opt \le e^{- 1/opt} </math>. Следовательно, <math>f(C_i) - 2 \le (n - 2) e^{-i/opt}</math>. | ||
i+1 = | |||
1) | |||
Выберем такое значение i, что <math>f(C_i) \ge opt + 2 > f(C_{i+1})</math>. Тогда <math>opt \le (n - 2) e^{-i/opt}</math> и <math>g - i \le opt \;</math>. | |||
где n = |V|. Заметим, что 1 - 1/ opt < | |||
g - i < | |||
Таким образом, | Таким образом, <math>g \le opt + i \le opt \left ( 1 + ln \frac{n - 2}{opt} \right ) </math>. | ||
Однако такой анализ является не вполне корректным. Далее будут рассмотрены некоторые конкретные вопросы и предложена новая общая техника анализа алгоритма | Однако такой анализ является не вполне корректным. Далее будут рассмотрены некоторые конкретные вопросы и предложена новая общая техника анализа жадного алгоритма аппроксимации с несубмодулярной гармонической функцией. | ||
== Основные результаты == | == Основные результаты == | ||
Роль субмодулярности | '''Роль субмодулярности''' | ||
Рассмотрим множество X и функцию f, определенную на множестве всех подмножеств <math>2^X \;</math>, то есть семействе всех подмножеств X. Функция f называется [[субмодулярная функция|субмодулярной]], если для любых двух подмножеств A и B в <math>2^X \;</math> выполняется неравенство | |||
<math>f(A) + f(B) \ge f(A \cap B) + f(A \cup B)</math>. | |||
В качестве примера рассмотрим связный граф G. Пусть X – множество вершин G. Функция -q(C), определенная в предыдущем разделе, является субмодулярной. Чтобы показать это, вначале рассмотрим свойства субмодулярных функций. | |||
Субмодулярная функция f называется [[нормализованная функция|нормализованной]], если <math>f( \empty ) = 0</math>. Каждая субмодулярная функция может быть нормализована посредством задания <math>g(A) = f(A) - f( \empty )</math>. Функция f является [[монотонно возрастающая функция|монотонно возрастающей]], если <math>f(A) \le f(B) \;</math> в случае <math>A \subset B \;</math>. Обозначим <math>\Delta_x f(A) = f(A \cup \{ x \} ) - f(A)</math>. | |||
'''Лемма 1'''. Функция <math>f: 2^X \to R</math> является субмодулярной в том и только том случае, если <math>\Delta_x f(A) \le \Delta_x f(B)</math> для любого <math>x \in X - B \;</math> и <math>A \subseteq B \;</math>. Кроме того, f является монотонно возрастающей в том и только том случае, если <math>\Delta_x f(A) \le \Delta_x f(B)</math> для любого <math>x \in B \;</math> и <math>A \subseteq B \;</math>. | |||
''Доказательство''. Если f является субмодулярной, то для <math>x \in X - B \;</math> и <math>A \subseteq B \;</math> имеет место соотношение | |||
<math>f(A \cup \{ x \} )+ f(B) \ge f((A \cup \{ x \} ) \cup B) + f(A \cup \{ x \} ) \cap B) = f(B \cup \{ x \} ) + f(A)</math>, | |||
иначе говоря, | |||
(1) <math>\Delta_x f(A) \ge \Delta_x f(B)</math>. | |||
Напротив, предположим, что свойство (1) выполняется для любого <math>x \in B \;</math> и <math>A \subseteq B \;</math>. Пусть C и D – два множества и <math>C \setminus D = \{ x_1, ..., x_k \}</math>. Тогда | |||
<math>f(C \cup D) - f(D) = \sum_{i=1}^k \Delta_{x_i} f(D \cup \{ x_1, ..., x_{i - 1} \} )</math> <math>\le \sum_{i=1}^k \Delta_{x_i} f((C \cap D) \cup \{ x_1, ..., x_{i - 1} \} )</math> <math>= f(C) - f(C \cap D)</math>. | |||
Если функция f является монотонно возрастающей, то <math>A \subseteq B \;</math> влечет <math>f(A) \le f(B)</math>. Следовательно, для <math>x \in B \;</math>, | |||
<math>\Delta_x f(A) \ge 0 = \Delta_x f(B)</math>. | |||
Напротив, если <math>\Delta_x f(A) \ge \Delta_x f(B)</math> для любого <math>x \in B \;</math> и <math>A \subseteq B \;</math>, тогда, для любых x и A, <math>\Delta_x f(A) \ge \Delta_x f(A \cup \{ x \} ) = 0</math>, то есть <math>f(A) \le f(A \cup \{ x \} )</math>. Пусть <math>B - A = \; \{ x_1, ..., x_k \}</math>. Тогда <math>f(A) \le f(A \cup \{ x_1 \} ) \le f(A \cup \{ x_1, x_2 \} ) \le ... \le f(B)</math>. | |||
Рассмотрим теперь субмодулярность -q(A). | |||
'''Лемма 2'''. Если <math>A \subset B \;</math>, то <math>\Delta_y q(A) \ge \Delta_y q(B)</math>. | |||
''Доказательство''. Заметим, что каждый связный компонент графа (v, D(B)) состоит из одного или нескольких связных компонентов графа (v, D(A)), поскольку <math>A \subset B \;</math>. Следовательно, количество связных компонентов (v, D(B)), доминируемых y, не превышает количества связных компонентов (v, D(A)), доминируемых y. Таким образом, лемма верна. | |||
A) | |||
Взаимоотношения между субмодулярными функциями и жадными алгоритмами рассматривались уже очень давно [3]. | Взаимоотношения между субмодулярными функциями и жадными алгоритмами рассматривались уже очень давно [3]. | ||
Пусть f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция. Рассмотрим задачу минимизации | Пусть f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция. Рассмотрим задачу минимизации | ||
min c(A) при условии A | |||
min c(A) | |||
при условии <math>A \in C_f</math>, | |||
где c – неотрицательная целевая функция, определенная на | где c – неотрицательная целевая функция, определенная на <math>2^X \;</math>, и <math>C_f = \{ C | f(C \cup \{ x \} ) - f(C) = 0</math> для всех <math>x \in X \} \;</math>. Существует жадный алгоритм, вычисляющий приближенное решение этой задачи. | ||
'''Жадный алгоритм B:''' | |||
Входные данные – субмодулярная функция f и целевая функция c; | |||
<math>A \gets \empty ;</math> | |||
'''while''' существует <math>x \in E \;</math>, такое, что <math>\Delta_x f(A) > 0 \;</math> | |||
'''do''' выбрать вершину x, максимизирующую <math>\Delta_x f(A)/c(x) \;</math>, и задать <math>A \gets A \cup \{ x \}</math> | |||
return A. | |||
| Строка 94: | Строка 118: | ||
Теорема 1. Если f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция, то жадный алгоритм B дает приближенное решение с коэффициентом аппроксимации H( | '''Теорема 1. Если f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция, то жадный алгоритм B дает приближенное решение с коэффициентом аппроксимации <math>H( \gamma) \;</math> от оптимального, где <math>\gamma = max_{x \in E} f( \{ x \} )</math>.''' | ||
'''Теорема 2. Пусть f – нормализованная, монотонно возрастающая, субмодулярная функция, а c – неотрицательная целевая функция. Если в процессе выполнения жадного алгоритма B выбираемое значение x всегда удовлетворяет условию <math>\Delta_x f(A_{i - 1})/c(x) \ge 1</math>, тогда он дает приближенное решение с коэффициентом аппроксимации <math>1 + ln(f^* /opt) \; </math> от оптимального для вышеприведенной задачи минимизации, где <math>f^* = f(A^*) \;</math> и <math>opt = c(A^*) \;</math> для оптимального решения <math>A^* \;</math>.''' | |||
Теперь вернемся к анализу жадного алгоритма A для MCDS. Кажется, что субмодулярность f в нем не используется. Однако на деле она используется в следующем утверждении: | Теперь вернемся к анализу жадного алгоритма A для MCDS. Кажется, что субмодулярность f в нем не используется. Однако на деле она используется в следующем утверждении: | ||
«Поскольку добавление C* к | «Поскольку добавление <math>C^* \; </math> к <math>C_i \;</math> уменьшит значение гармонической функции с <math>f(C_i) \;</math> до 2, значение f, уменьшенной на вершину из <math>C^* \;</math>, будет в среднем составлять <math>(f(C_i) - 2)/opt \;</math>. Согласно жадному правилу выбора <math>x_i + 1 \;</math>, должно иметь место соотношение <math>f(C_i) - f(C_{i + 1}) \ge \frac{f(C_i) - 2}{opt}</math>». | ||
Чтобы убедиться в этом, рассмотрим утверждение более внимательно. | Чтобы убедиться в этом, рассмотрим утверждение более внимательно. | ||
Пусть <math>C^* = \{ y_i, ..., у_opt \} \;</math>; обозначим <math>C^*_j = \{ y_1, ..., y_j \} </math>. Тогда | |||
<math>f(C_i) - 2 = f(C_i) - f(C_i \cup C^*) = \sum_{j=1}^{opt} [f(C_i \cup C^*_{j - 1}) - f(C_i \cup C^*_j) ] </math>, | |||
где <math>C^*_0 = \empty \;</math>. Согласно жадному правилу выбора <math>x_i + 1 \;</math>, должно иметь место соотношение <math>f(C_i) - f(C_{i + 1}) \ge f(C_i) - f(C_i \cup \{ y_i \} )</math> для <math>j = 1, ..., opt \;</math>. Следовательно, для того, чтобы выполнялось | |||
<math>f(C_i) - f(C_{i + 1}) \ge \frac{f(C_i) - 2}{opt}</math>, | |||
должно выполняться соотношение | |||
(2) <math> - \Delta_{y_j} f(C_i) = f(C_i) - f(C_i \; \cup \; \{ y_j \} ) \ge f(C_i \; \cup \; C^*_{j - 1}) - f(C_i \; \cup \; C^*_j) = - \Delta_{y_j} f(C_i \; \cup\; C^*_{j - 1})</math>. | |||
| Строка 117: | Строка 152: | ||
Отказ от субмодулярности | '''Отказ от субмодулярности''' | ||
Отказ от субмодулярности – непростой вопрос, уже долгое время остающийся открытым. Однако это возможно благодаря наблюдению Дю и коллег относительно утверждения (2) в [1]: субмодулярность –f применяется для приращения вершины <math>y_j \;</math>, принадлежащей к оптимальному решению <math>C^* \;</math>. | |||
В силу гибкости упорядочения вершин <math>y_j \;</math> можно организовать его таким образом, чтобы контролировать величину <math>\Delta_{y_j} f(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1} )</math>. Это позволит успешно справиться с задачей MCDS. | |||
'''Лемма 3'''. Пусть значения <math>y_j \;</math> упорядочены таким образом, что для любого <math>j = 1, ..., opt \;</math> последовательность <math>\{ y_1, ..., y_j \} \;</math> порождает связный подграф. Тогда <math>\Delta_{y_j} f(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1}) \le 1</math>. | |||
''Доказательство''. Поскольку все <math>y_1, ..., y_{j - 1} \;</math> являются связными, <math>y_j \;</math> может доминировать не более одного дополнительного связного компонента в подграфе, порожденном <math>C_{i - 1} \cup C^*_{j - 1} \;</math> , относительно подграфа, порожденного <math>C_{i - 1} \;</math>. Следовательно, <math>\Delta_{y_j} p(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1}) \le 1</math>. | |||
Более того, поскольку –q является субмодулярной, <math>\Delta_{y_j} q(C_i) - \Delta_{y_j} q(C_i \cup C^*_{j - 1}) \le 0</math>. | |||
Таким образом, <math>\Delta_{y_j} f(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1}) \le 1</math>. | |||
Таким образом, | |||
Теперь можно провести корректный анализ жадного алгоритма A для MCDS [4]. Согласно лемме 3 | Теперь можно провести корректный анализ жадного алгоритма A для MCDS [4]. Согласно лемме 3, <math>f(C_i) - f(C_{i + 1}) \ge \frac{f(C_i) - 2}{opt} - 1</math>. | ||
Следовательно, | Следовательно, <math>f(C_{i + 1}) - 2 - opt \le (f(C_i) - 2 + opt) \left ( 1 - \frac{1}{opt} \right ) \le (f( \empty ) - 2 - opt) \left ( 1 - \frac{1}{opt} \right )^{i + 1} = (n - 2 - opt) \left ( 1 - \frac{1}{opt} \right )^{i + 1}</math>, | ||
f( | |||
= (n - 2 - opt) ( 1 - 1 opt | |||
где <math>n = |V| \;</math>. Заметим, что <math>1 - 1/opt \le e^{-1/opt}</math>. Таким образом, <math>f(C_i) - 2 - opt \le (n - 2) e^{ -i/opt}</math>. | |||
f( | |||
opt | |||
Выберем такое <math>i \;</math>, чтобы выполнялось <math>f(C_i) \ge 2 \cdot opt + 2 > f(C_{i+1})</math>. Тогда <math>opt \le (n - 2) e^{ -i/opt}</math> и <math>g - i \le 2 \cdot opt \;</math>. | |||
и | |||
< | |||
g | |||
Следовательно, <math>g \le 2 \cdot opt + i \le opt \left ( 2 + ln \frac {n - 2} {opt} \right ) \le opt (2 + ln \; \delta)</math>, где <math>\delta \;</math> – максимальная степень исходного графа G. | |||
== Применение == | == Применение == | ||
| Строка 158: | Строка 193: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Можно ли определить коэффициент эффективности 1 + H( | Можно ли определить коэффициент эффективности <math>1 + H( \delta) \;</math> для жадного алгоритма B в задаче MCDS? Ответ неизвестен. Неизвестно также, как получить четкое обобщение теоремы 1. | ||
== См. также == | == См. также == | ||
* ''[[Связное доминирующее множество]] | * ''[[Связное доминирующее множество]] | ||
* ''[[Алгоритмы локального поиска для | * ''[[Алгоритмы локального поиска для k-КНФ]] | ||
* ''[[Деревья Штейнера]] | * ''[[Деревья Штейнера]] | ||
== Литература == | == Литература == | ||
Текущая версия от 14:41, 1 октября 2023
Ключевые слова и синонимы
Техника анализа жадной аппроксимации
Постановка задачи
Рассмотрим граф G = (V, E). Множество C множества V называется доминирующим множеством, если каждая вершина либо принадлежит к C, либо смежна с вершиной, принадлежащей к C. Если подграф, порожденный С, является связным, то C называется связным доминирующим множеством. Пусть дан связный граф G; необходимо найти связное доминирующее множество минимальной мощности. Эта задача имеет обозначение MCDS и является NP-полной. Ее оптимальное решение называется минимальным связным доминирующим множеством. Рассмотрим жадную аппроксимацию с гармонической функцией f.
Жадный алгоритм A:
[math]\displaystyle{ C \leftarrow \empty }[/math]
while [math]\displaystyle{ f(C) \gt 2 ;\ }[/math] do
выбрать вершину x так, чтобы максимизировать [math]\displaystyle{ f(C) - f(C \cup \{ x \} ) }[/math] и [math]\displaystyle{ C \leftarrow C \cup \{ x \} }[/math]; вывести C.
Здесь f определяется как f(C) = p(C) + q(C), где p(C) – количество связных компонент подграфа, порожденного C, а q(C) – количество связных компонент подграфа с множеством вершин V и множеством дуг [math]\displaystyle{ \{ (u, v) \in E | u \in C }[/math] или [math]\displaystyle{ v \in C \} }[/math]. Функция f обладает важным свойством: C является связным доминирующим множеством в том и только том случае, если f(C) = 2.
Если C является связным доминирующим множеством, то p(C) = q(C) = 1 и, следовательно, f(C) = 2. Напротив, предположим, что [math]\displaystyle{ f(C \cup \{ x \}) = 2 }[/math]. Поскольку [math]\displaystyle{ p(C) \ge 1 \; }[/math] и [math]\displaystyle{ q(C) \ge 1 \; }[/math], должно иметь место p(C) = q(C) = 1, из чего следует, что C является связным доминирующим множеством. Функция f обладает еще одним свойством на графе G, имеющем не менее трех вершин: если f(C) > 2, то существует [math]\displaystyle{ x \in V \; }[/math], такое, что [math]\displaystyle{ f(C) - f(C \cup \{ x \} ) \gt 0 }[/math]. Фактически, для [math]\displaystyle{ C \ne \empty \; }[/math], поскольку G является связным графом, имеющим не менее трех вершин, должна существовать вершина x со степенью не ниже двух, и для такой вершины x выполняется [math]\displaystyle{ f(C \cup \{ x \}) \lt f(C) }[/math]. Для случая [math]\displaystyle{ C \ne \empty \; }[/math] рассмотрим связную компоненту подграфа, порожденного C. Обозначим как B его множество вершин, являющееся подмножеством C. Для каждой вершины y, смежной с B, в случае, если y смежна с вершиной, не смежной с B и не принадлежащей к C, то [math]\displaystyle{ p(C \cup \{ y \} ) \lt p(C) }[/math] и [math]\displaystyle{ q(C \cup \{ y \} ) \le q(C) }[/math]; если вершина y смежна с вершиной из множества C — B, то [math]\displaystyle{ p(C \cup \{ y \} ) \le p(C) }[/math] и [math]\displaystyle{ q(C \cup \{ y \} ) \lt q(C) }[/math].
Проведем некоторый анализ вышеприведенного жадного алгоритма: Пусть [math]\displaystyle{ x_1, ..., x_g \; }[/math] – вершины, выбранные жадным алгоритмом в порядке их появления в алгоритме. Введем обозначение [math]\displaystyle{ C_i = \{ x_1, ... , x_i \} \; }[/math]. Пусть [math]\displaystyle{ C^* = \{ y_1, ..., y_{opt} \} \; }[/math] – минимальное связное доминирующее множество. Поскольку добавление [math]\displaystyle{ C^* \; }[/math] к [math]\displaystyle{ C_i \; }[/math] уменьшит значение гармонической функции с [math]\displaystyle{ f(C_i) \; }[/math] до 2, значение f, уменьшенной на вершину из [math]\displaystyle{ C^* \; }[/math], будет в среднем составлять [math]\displaystyle{ (f(C_i) - 2)/opt \; }[/math]. Но, согласно жадному правилу выбора [math]\displaystyle{ x_i + 1 \; }[/math], должно иметь место соотношение [math]\displaystyle{ f(C_i) - f(C_{i + 1}) \ge \frac{f(C_i) - 2}{opt} }[/math].
Следовательно, [math]\displaystyle{ f(C_{i + 1}) - 2 \le (f(C_i) - 2) (1 - \frac{1}{opt}) \le (f( \empty ) - 2) (1 - \frac{1}{opt})^{i + 1} = (n - 2) (1 - \frac{1}{opt})^{i + 1} }[/math],
где [math]\displaystyle{ n = |V| \; }[/math]. Заметим, что [math]\displaystyle{ 1 - 1/ opt \le e^{- 1/opt} }[/math]. Следовательно, [math]\displaystyle{ f(C_i) - 2 \le (n - 2) e^{-i/opt} }[/math].
Выберем такое значение i, что [math]\displaystyle{ f(C_i) \ge opt + 2 \gt f(C_{i+1}) }[/math]. Тогда [math]\displaystyle{ opt \le (n - 2) e^{-i/opt} }[/math] и [math]\displaystyle{ g - i \le opt \; }[/math].
Таким образом, [math]\displaystyle{ g \le opt + i \le opt \left ( 1 + ln \frac{n - 2}{opt} \right ) }[/math].
Однако такой анализ является не вполне корректным. Далее будут рассмотрены некоторые конкретные вопросы и предложена новая общая техника анализа жадного алгоритма аппроксимации с несубмодулярной гармонической функцией.
Основные результаты
Роль субмодулярности
Рассмотрим множество X и функцию f, определенную на множестве всех подмножеств [math]\displaystyle{ 2^X \; }[/math], то есть семействе всех подмножеств X. Функция f называется субмодулярной, если для любых двух подмножеств A и B в [math]\displaystyle{ 2^X \; }[/math] выполняется неравенство
[math]\displaystyle{ f(A) + f(B) \ge f(A \cap B) + f(A \cup B) }[/math].
В качестве примера рассмотрим связный граф G. Пусть X – множество вершин G. Функция -q(C), определенная в предыдущем разделе, является субмодулярной. Чтобы показать это, вначале рассмотрим свойства субмодулярных функций.
Субмодулярная функция f называется нормализованной, если [math]\displaystyle{ f( \empty ) = 0 }[/math]. Каждая субмодулярная функция может быть нормализована посредством задания [math]\displaystyle{ g(A) = f(A) - f( \empty ) }[/math]. Функция f является монотонно возрастающей, если [math]\displaystyle{ f(A) \le f(B) \; }[/math] в случае [math]\displaystyle{ A \subset B \; }[/math]. Обозначим [math]\displaystyle{ \Delta_x f(A) = f(A \cup \{ x \} ) - f(A) }[/math].
Лемма 1. Функция [math]\displaystyle{ f: 2^X \to R }[/math] является субмодулярной в том и только том случае, если [math]\displaystyle{ \Delta_x f(A) \le \Delta_x f(B) }[/math] для любого [math]\displaystyle{ x \in X - B \; }[/math] и [math]\displaystyle{ A \subseteq B \; }[/math]. Кроме того, f является монотонно возрастающей в том и только том случае, если [math]\displaystyle{ \Delta_x f(A) \le \Delta_x f(B) }[/math] для любого [math]\displaystyle{ x \in B \; }[/math] и [math]\displaystyle{ A \subseteq B \; }[/math].
Доказательство. Если f является субмодулярной, то для [math]\displaystyle{ x \in X - B \; }[/math] и [math]\displaystyle{ A \subseteq B \; }[/math] имеет место соотношение
[math]\displaystyle{ f(A \cup \{ x \} )+ f(B) \ge f((A \cup \{ x \} ) \cup B) + f(A \cup \{ x \} ) \cap B) = f(B \cup \{ x \} ) + f(A) }[/math],
иначе говоря,
(1) [math]\displaystyle{ \Delta_x f(A) \ge \Delta_x f(B) }[/math].
Напротив, предположим, что свойство (1) выполняется для любого [math]\displaystyle{ x \in B \; }[/math] и [math]\displaystyle{ A \subseteq B \; }[/math]. Пусть C и D – два множества и [math]\displaystyle{ C \setminus D = \{ x_1, ..., x_k \} }[/math]. Тогда
[math]\displaystyle{ f(C \cup D) - f(D) = \sum_{i=1}^k \Delta_{x_i} f(D \cup \{ x_1, ..., x_{i - 1} \} ) }[/math] [math]\displaystyle{ \le \sum_{i=1}^k \Delta_{x_i} f((C \cap D) \cup \{ x_1, ..., x_{i - 1} \} ) }[/math] [math]\displaystyle{ = f(C) - f(C \cap D) }[/math].
Если функция f является монотонно возрастающей, то [math]\displaystyle{ A \subseteq B \; }[/math] влечет [math]\displaystyle{ f(A) \le f(B) }[/math]. Следовательно, для [math]\displaystyle{ x \in B \; }[/math],
[math]\displaystyle{ \Delta_x f(A) \ge 0 = \Delta_x f(B) }[/math].
Напротив, если [math]\displaystyle{ \Delta_x f(A) \ge \Delta_x f(B) }[/math] для любого [math]\displaystyle{ x \in B \; }[/math] и [math]\displaystyle{ A \subseteq B \; }[/math], тогда, для любых x и A, [math]\displaystyle{ \Delta_x f(A) \ge \Delta_x f(A \cup \{ x \} ) = 0 }[/math], то есть [math]\displaystyle{ f(A) \le f(A \cup \{ x \} ) }[/math]. Пусть [math]\displaystyle{ B - A = \; \{ x_1, ..., x_k \} }[/math]. Тогда [math]\displaystyle{ f(A) \le f(A \cup \{ x_1 \} ) \le f(A \cup \{ x_1, x_2 \} ) \le ... \le f(B) }[/math].
Рассмотрим теперь субмодулярность -q(A).
Лемма 2. Если [math]\displaystyle{ A \subset B \; }[/math], то [math]\displaystyle{ \Delta_y q(A) \ge \Delta_y q(B) }[/math].
Доказательство. Заметим, что каждый связный компонент графа (v, D(B)) состоит из одного или нескольких связных компонентов графа (v, D(A)), поскольку [math]\displaystyle{ A \subset B \; }[/math]. Следовательно, количество связных компонентов (v, D(B)), доминируемых y, не превышает количества связных компонентов (v, D(A)), доминируемых y. Таким образом, лемма верна.
Взаимоотношения между субмодулярными функциями и жадными алгоритмами рассматривались уже очень давно [3].
Пусть f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция. Рассмотрим задачу минимизации
min c(A)
при условии [math]\displaystyle{ A \in C_f }[/math],
где c – неотрицательная целевая функция, определенная на [math]\displaystyle{ 2^X \; }[/math], и [math]\displaystyle{ C_f = \{ C | f(C \cup \{ x \} ) - f(C) = 0 }[/math] для всех [math]\displaystyle{ x \in X \} \; }[/math]. Существует жадный алгоритм, вычисляющий приближенное решение этой задачи.
Жадный алгоритм B:
Входные данные – субмодулярная функция f и целевая функция c;
[math]\displaystyle{ A \gets \empty ; }[/math]
while существует [math]\displaystyle{ x \in E \; }[/math], такое, что [math]\displaystyle{ \Delta_x f(A) \gt 0 \; }[/math]
do выбрать вершину x, максимизирующую [math]\displaystyle{ \Delta_x f(A)/c(x) \; }[/math], и задать [math]\displaystyle{ A \gets A \cup \{ x \} }[/math]
return A.
Следующие два результата хорошо известны.
Теорема 1. Если f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция, то жадный алгоритм B дает приближенное решение с коэффициентом аппроксимации [math]\displaystyle{ H( \gamma) \; }[/math] от оптимального, где [math]\displaystyle{ \gamma = max_{x \in E} f( \{ x \} ) }[/math].
Теорема 2. Пусть f – нормализованная, монотонно возрастающая, субмодулярная функция, а c – неотрицательная целевая функция. Если в процессе выполнения жадного алгоритма B выбираемое значение x всегда удовлетворяет условию [math]\displaystyle{ \Delta_x f(A_{i - 1})/c(x) \ge 1 }[/math], тогда он дает приближенное решение с коэффициентом аппроксимации [math]\displaystyle{ 1 + ln(f^* /opt) \; }[/math] от оптимального для вышеприведенной задачи минимизации, где [math]\displaystyle{ f^* = f(A^*) \; }[/math] и [math]\displaystyle{ opt = c(A^*) \; }[/math] для оптимального решения [math]\displaystyle{ A^* \; }[/math].
Теперь вернемся к анализу жадного алгоритма A для MCDS. Кажется, что субмодулярность f в нем не используется. Однако на деле она используется в следующем утверждении:
«Поскольку добавление [math]\displaystyle{ C^* \; }[/math] к [math]\displaystyle{ C_i \; }[/math] уменьшит значение гармонической функции с [math]\displaystyle{ f(C_i) \; }[/math] до 2, значение f, уменьшенной на вершину из [math]\displaystyle{ C^* \; }[/math], будет в среднем составлять [math]\displaystyle{ (f(C_i) - 2)/opt \; }[/math]. Согласно жадному правилу выбора [math]\displaystyle{ x_i + 1 \; }[/math], должно иметь место соотношение [math]\displaystyle{ f(C_i) - f(C_{i + 1}) \ge \frac{f(C_i) - 2}{opt} }[/math]».
Чтобы убедиться в этом, рассмотрим утверждение более внимательно.
Пусть [math]\displaystyle{ C^* = \{ y_i, ..., у_opt \} \; }[/math]; обозначим [math]\displaystyle{ C^*_j = \{ y_1, ..., y_j \} }[/math]. Тогда
[math]\displaystyle{ f(C_i) - 2 = f(C_i) - f(C_i \cup C^*) = \sum_{j=1}^{opt} [f(C_i \cup C^*_{j - 1}) - f(C_i \cup C^*_j) ] }[/math],
где [math]\displaystyle{ C^*_0 = \empty \; }[/math]. Согласно жадному правилу выбора [math]\displaystyle{ x_i + 1 \; }[/math], должно иметь место соотношение [math]\displaystyle{ f(C_i) - f(C_{i + 1}) \ge f(C_i) - f(C_i \cup \{ y_i \} ) }[/math] для [math]\displaystyle{ j = 1, ..., opt \; }[/math]. Следовательно, для того, чтобы выполнялось
[math]\displaystyle{ f(C_i) - f(C_{i + 1}) \ge \frac{f(C_i) - 2}{opt} }[/math],
должно выполняться соотношение
(2) [math]\displaystyle{ - \Delta_{y_j} f(C_i) = f(C_i) - f(C_i \; \cup \; \{ y_j \} ) \ge f(C_i \; \cup \; C^*_{j - 1}) - f(C_i \; \cup \; C^*_j) = - \Delta_{y_j} f(C_i \; \cup\; C^*_{j - 1}) }[/math].
Для (2) требуется субмодулярность –f. Однако, к сожалению, –f не является субмодулярной. Контрпример можно найти в работе [3]. Именно поэтому анализ жадного алгоритма A в разделе «Постановка задачи» неверен.
Отказ от субмодулярности
Отказ от субмодулярности – непростой вопрос, уже долгое время остающийся открытым. Однако это возможно благодаря наблюдению Дю и коллег относительно утверждения (2) в [1]: субмодулярность –f применяется для приращения вершины [math]\displaystyle{ y_j \; }[/math], принадлежащей к оптимальному решению [math]\displaystyle{ C^* \; }[/math].
В силу гибкости упорядочения вершин [math]\displaystyle{ y_j \; }[/math] можно организовать его таким образом, чтобы контролировать величину [math]\displaystyle{ \Delta_{y_j} f(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1} ) }[/math]. Это позволит успешно справиться с задачей MCDS.
Лемма 3. Пусть значения [math]\displaystyle{ y_j \; }[/math] упорядочены таким образом, что для любого [math]\displaystyle{ j = 1, ..., opt \; }[/math] последовательность [math]\displaystyle{ \{ y_1, ..., y_j \} \; }[/math] порождает связный подграф. Тогда [math]\displaystyle{ \Delta_{y_j} f(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1}) \le 1 }[/math].
Доказательство. Поскольку все [math]\displaystyle{ y_1, ..., y_{j - 1} \; }[/math] являются связными, [math]\displaystyle{ y_j \; }[/math] может доминировать не более одного дополнительного связного компонента в подграфе, порожденном [math]\displaystyle{ C_{i - 1} \cup C^*_{j - 1} \; }[/math] , относительно подграфа, порожденного [math]\displaystyle{ C_{i - 1} \; }[/math]. Следовательно, [math]\displaystyle{ \Delta_{y_j} p(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1}) \le 1 }[/math].
Более того, поскольку –q является субмодулярной, [math]\displaystyle{ \Delta_{y_j} q(C_i) - \Delta_{y_j} q(C_i \cup C^*_{j - 1}) \le 0 }[/math].
Таким образом, [math]\displaystyle{ \Delta_{y_j} f(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1}) \le 1 }[/math].
Теперь можно провести корректный анализ жадного алгоритма A для MCDS [4]. Согласно лемме 3, [math]\displaystyle{ f(C_i) - f(C_{i + 1}) \ge \frac{f(C_i) - 2}{opt} - 1 }[/math].
Следовательно, [math]\displaystyle{ f(C_{i + 1}) - 2 - opt \le (f(C_i) - 2 + opt) \left ( 1 - \frac{1}{opt} \right ) \le (f( \empty ) - 2 - opt) \left ( 1 - \frac{1}{opt} \right )^{i + 1} = (n - 2 - opt) \left ( 1 - \frac{1}{opt} \right )^{i + 1} }[/math],
где [math]\displaystyle{ n = |V| \; }[/math]. Заметим, что [math]\displaystyle{ 1 - 1/opt \le e^{-1/opt} }[/math]. Таким образом, [math]\displaystyle{ f(C_i) - 2 - opt \le (n - 2) e^{ -i/opt} }[/math].
Выберем такое [math]\displaystyle{ i \; }[/math], чтобы выполнялось [math]\displaystyle{ f(C_i) \ge 2 \cdot opt + 2 \gt f(C_{i+1}) }[/math]. Тогда [math]\displaystyle{ opt \le (n - 2) e^{ -i/opt} }[/math] и [math]\displaystyle{ g - i \le 2 \cdot opt \; }[/math].
Следовательно, [math]\displaystyle{ g \le 2 \cdot opt + i \le opt \left ( 2 + ln \frac {n - 2} {opt} \right ) \le opt (2 + ln \; \delta) }[/math], где [math]\displaystyle{ \delta \; }[/math] – максимальная степень исходного графа G.
Применение
У вышеприведенной техники множество приложений, включая анализ итеративных 1-деревьев Штейнера в задаче нахождения минимального дерева Штейнера и анализ жадных аппроксимаций для задач оптимизации в оптических сетях [4] и беспроводных сетях [3].
Открытые вопросы
Можно ли определить коэффициент эффективности [math]\displaystyle{ 1 + H( \delta) \; }[/math] для жадного алгоритма B в задаче MCDS? Ответ неизвестен. Неизвестно также, как получить четкое обобщение теоремы 1.
См. также
Литература
1. Du, D.-Z., Graham, R.L., Pardalos, P.M., Wan, P.-J., Wu, W., Zhao, W.: Analysis of greedy approximations with nonsubmodular potential functions. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008 3. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, Hoboken (1999) 4. Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., Ko, K.-I.: A greedy approximation for minimum connected dominating set. Theor. Comput. Sci. 329, 325-330 (2004) 5. Ruan, L., Wu, W.: Broadcast routing with minimum wavelength conversion in WDM optical networks. J. Comb. Optim. 9 223-235 (2005)