Жадные алгоритмы аппроксимации: различия между версиями

Материал из WEGA
мНет описания правки
 
(не показано 26 промежуточных версий этого же участника)
Строка 37: Строка 37:




Однако такой анализ является не вполне корректным. Далее будут рассмотрены некоторые конкретные вопросы и предложена новая общая техника анализа алгоритма жадной аппроксимации с несубмодулярной гармонической функцией.
Однако такой анализ является не вполне корректным. Далее будут рассмотрены некоторые конкретные вопросы и предложена новая общая техника анализа жадного алгоритма аппроксимации с несубмодулярной гармонической функцией.


== Основные результаты ==
== Основные результаты ==


Роль субмодулярности
'''Роль субмодулярности'''




Рассмотрим множество X и функцию f, определенную на множестве всех подмножеств 2X, то есть семействе всех подмножеств X. Функция f называется субмодулярной, если для любых двух подмножеств A и B в 2X выполняется
Рассмотрим множество X и функцию f, определенную на множестве всех подмножеств <math>2^X \;</math>, то есть семействе всех подмножеств X. Функция f называется [[субмодулярная функция|субмодулярной]], если для любых двух подмножеств A и B в <math>2^X \;</math> выполняется неравенство
f(A) + f(B) > f(A \ B) + f(A [ B) :
В качестве примера рассмотрим связный граф G. Пусть X – множество вершин G. Функция—q(C), определенная в предыдущем разделе, является субмодулярной. Чтобы показать это, вначале рассмотрим свойства субмодулярных функций.




Субмодулярная функция f называется нормализованной, если f(;) = 0. Каждая субмодулярная функция может быть нормализована посредством задания g(A) = f(A) — f(;). Функция f является монотонно возрастающей, если f (A) < f(B) для ACB. Обозначим Axf(A) = f(A [ fxg) -f(A).
<math>f(A) + f(B) \ge f(A \cap B) + f(A \cup B)</math>.
Лемма 1. Функция f:2X!R является субмодулярной в том и только том случае, если Axf(A) < Axf(B) для любого x 2 X - B и A С B. Кроме того, f является монотонно возрастающей в том и только том случае, если Axf(A) < Axf(B) для любого x2B и ACB.




Доказательство. Если f является субмодулярной, то для x 2 X — B и ACJJ имеет место
В качестве примера рассмотрим связный граф G. Пусть X – множество вершин G. Функция -q(C), определенная в предыдущем разделе, является субмодулярной. Чтобы показать это, вначале рассмотрим свойства субмодулярных функций.
f(A[fxg)+ > f((A [ fxg) [ B) + f(A [ fxg) \ B) = f(B[fxg) + f(
это означает, что
Axf(A) > Axf(B) :
(1)
к
к
Напротив, предположим, что свойство (1) выполняется для любого x 2 B и AC B. Пусть C и D – два множества и C n D = fx1,..x k g. Тогда
U
f(C [ D) - f(D) =
х|Ч)


Если функция f является монотонно возрастающей, то для ACB f(A) < f(B). Следовательно, для x 2 B,
A)xf{A) > 0 = Axf(B) :
Напротив, если Axf(A) > Axf(B) для любого x 2 B и А С B, тогда для любых x и A, Axf(A) > Axf(AU{x}) = 0, то есть f(A) < /(A U xg). Пусть B - A = fx 1..: ; xk g. Тогда
f(A) </(AU
</(AU {xux2}) < ••• </


Рассмотрим теперь субмодулярность of—q(A). Лемма 2. Если A С B, то Ayq(A) > Ayq(B).
Субмодулярная функция 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. Таким образом, лемма верна.
 


Доказательство. Заметим, что каждый связный компонент графа (v, D(B)) состоит из одного или нескольких связных компонентов графа (v, D(A)), поскольку A С B. Следовательно, количество связных компонентов (v, D(B)), доминируемых y, не превышает количества связных компонентов (v, D(A)), доминируемых y. Таким образом, лемма верна.
Взаимоотношения между субмодулярными функциями и жадными алгоритмами рассматривались уже очень давно [3].
Взаимоотношения между субмодулярными функциями и жадными алгоритмами рассматривались уже очень давно [3].
Пусть f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция. Рассмотрим задачу минимизации
Пусть f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция. Рассмотрим задачу минимизации
min    c(A) при условии    A 2 Cf :
 
min    c(A)
 
при условии    <math>A \in C_f</math>,
   
   
где c – неотрицательная целевая функция, определенная на 2X, и Cf = fCj f(C [ fxg) - f(C) = 0 для всех x 2 Xg. Существует жадный алгоритм, вычисляющий приближенное решение этой задачи.
где 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>


Жадный алгоритм B:
return A.
входные данные – субмодулярная функция f и целевая функция c;
while существует x 2 E, такое, что Axf(A) > 0
do выбрать вершину x, максимизирующую Axf(A)/c(x), и задать
A^AU {x}\ return A.




Строка 91: Строка 118:




Теорема 1. Если f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция, то жадный алгоритм B дает приближенное решение с коэффициентом аппроксимации H(y) от оптимального, где у = maxx2E f(fxg).
'''Теорема 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>.'''




Теорема 2. Пусть f – нормализованная, монотонно возрастающая, субмодулярная функция, а c – неотрицательная целевая функция. Если в процессе выполнения жадного алгоритма B выбираемое значение x всегда удовлетворяет условию Axf(Aj-i)/c(x) > 1, тогда он дает приближенное решение с коэффициентом аппроксимации 1 + ln(/* /opt) от оптимального для вышеприведенной задачи минимизации, где f* = f(A*) и opt = c(A*) для оптимального решения A*.
Теперь вернемся к анализу жадного алгоритма A для MCDS. Кажется, что субмодулярность f в нем не используется. Однако на деле она используется в следующем утверждении:
Теперь вернемся к анализу жадного алгоритма A для MCDS. Кажется, что субмодулярность f в нем не используется. Однако на деле она используется в следующем утверждении:
«Поскольку добавление C* к Ci уменьшит значение гармонической функции с f(Ci) до 2, значение f, уменьшенной на вершину из C*, будет в среднем составлять (f(Ci) 2)/opt. Но, согласно жадному правилу выбора xi + 1, должно иметь место
«Поскольку добавление <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>».




Чтобы убедиться в этом, рассмотрим утверждение более внимательно.
Чтобы убедиться в этом, рассмотрим утверждение более внимательно.
Пусть C* = {yi,... , уopt}; обозначим C* = {yx,... , у,}. Тогда
/(C,)-2=/(C,)-/(C,UC*)
opt
= J2lf(C,UC*_1)-f(ClUC*)]


Пусть <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>.


(2)
для j = 1; : : : ; opt. Следовательно, необходимо -Ayjf(Ci)=f(Ci)-f(CiU{yj}),
чтобы выполнялось




Строка 114: Строка 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>.


Отказ от субмодулярности – непростой вопрос, уже долгое время остающийся открытым. Однако это возможно благодаря наблюдению Дю и коллег относительно утверждения (2) в [1]: субмодулярность –f применяется для приращения вершины yj, принадлежащей к оптимальному решению C*.
В силу гибкости упорядочения yj можно организовать его таким образом, чтобы контролировать Ayjfid) - Ayjf(d U C*_x). Это позволит успешно справиться с задачей MCDS.




Лемма 3. Пусть значения yj упорядочены таким образом, что для любого j = 1..: ; opt, fy1..: ; yjg порождает связный подграф. Тогда
''Доказательство''. Поскольку все <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>.
{ [ Cj_r) <




Доказательство. Поскольку все y 1..: ; y^-\ являются связными, yj может доминировать не более одного дополнительного связного компонента в подграфе, порожденном C,_i [ C*_x, относительно подграфа, порожденного c i — 1.  
Более того, поскольку –q является субмодулярной, <math>\Delta_{y_j} q(C_i) - \Delta_{y_j} q(C_i \cup C^*_{j - 1}) \le 0</math>.




Более того, поскольку–q является субмодулярной,
Таким образом, <math>\Delta_{y_j} f(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1}) \le 1</math>.
Таким образом,


где C* = ;. Но, согласно жадному правилу выбора xi + 1, должно иметь место
f(Ci) -/(Q+1) > f(Ci) -/(C, U yjg)


Теперь можно провести корректный анализ жадного алгоритма 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(Ci+1) -2-opt< (f(Ci) - 2 + opt) 1 - 1 <(/(0)-2-o,f)(l--L)H
 
= (n - 2 - opt) ( 1 - 1 opt
 
where n = jVj. Note that 1 - 1/opt < е~11оР(. Hence,
где <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(Ci) -2-opt<(n- 2)e~ilopt : Choose i such that f(Ci) > 2 • opt + 2 > f(Ci+1). Then
 
opt <{n-2)e-ilopt and
g - i < 2 ■ opt :
Therefore,
и-2 opt
< opt(2 +ln<5)
g < 2 ■ opt + i < opt  2 + ln
где S – максимальная степень исходного графа G.


Выберем такое <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>.
Следовательно, <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.


== Применение ==
== Применение ==
Строка 155: Строка 193:


== Открытые вопросы ==
== Открытые вопросы ==
Можно ли определить коэффициент эффективности 1 + H(S) для жадного алгоритма B в задаче MCDS? Ответ неизвестен. Неизвестно также, как получить четкое обобщение теоремы 1.
Можно ли определить коэффициент эффективности <math>1 + H( \delta) \;</math> для жадного алгоритма B в задаче MCDS? Ответ неизвестен. Неизвестно также, как получить четкое обобщение теоремы 1.
 


== См. также ==
== См. также ==
* ''[[Связное доминирующее множество]]
* ''[[Связное доминирующее множество]]
* ''[[Алгоритмы локального поиска для kSAT]]
* ''[[Алгоритмы локального поиска для 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)