Просмотр кода страницы Жадные алгоритмы аппроксимации

== Ключевые слова и синонимы ==
Техника анализа жадной аппроксимации


== Постановка задачи ==
Рассмотрим граф G = (V, E). Множество C множества V называется [[доминирующее множество|доминирующим множеством]], если каждая вершина либо принадлежит к C, либо смежна с вершиной, принадлежащей к C. Если подграф, порожденный С, является связным, то C называется [[связное доминирующее множество|связным доминирующим множеством]].
Пусть дан связный граф G; необходимо найти связное доминирующее множество минимальной мощности. Эта задача имеет обозначение MCDS и является NP-полной. Ее оптимальное решение называется минимальным связным доминирующим множеством. Рассмотрим жадную аппроксимацию с гармонической функцией f.


'''Жадный алгоритм 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>,


где <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, что <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>.


Таким образом, <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. Таким образом, лемма верна.


Взаимоотношения между субмодулярными функциями и жадными алгоритмами рассматривались уже очень давно [3].

Пусть f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция. Рассмотрим задачу минимизации

min    c(A)

при условии    <math>A \in C_f</math>,
 
где 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.


Следующие два результата хорошо известны.


'''Теорема 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 в нем не используется. Однако на деле она используется в следующем утверждении:
«Поскольку добавление <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*)]


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


Для (2) требуется субмодулярность –f. Однако, к сожалению, –f не является субмодулярной. Контрпример можно найти в работе [3]. Именно поэтому анализ жадного алгоритма A в разделе «Постановка задачи» неверен.


Отказ от субмодулярности

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


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


Доказательство. Поскольку все y 1..: ; y^-\ являются связными, yj может доминировать не более одного дополнительного связного компонента в подграфе, порожденном C,_i [ C*_x, относительно подграфа, порожденного c i — 1. 


Более того, поскольку–q является субмодулярной,
Таким образом,

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

Теперь можно провести корректный анализ жадного алгоритма A для MCDS [4]. Согласно лемме 3

 
Следовательно,
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,
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.

== Применение ==
У вышеприведенной техники множество приложений, включая анализ итеративных 1-деревьев Штейнера в задаче нахождения минимального дерева Штейнера и анализ жадных аппроксимаций для задач оптимизации в оптических сетях [4] и беспроводных сетях [3].


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


== См. также ==
* ''[[Связное доминирующее множество]]
* ''[[Алгоритмы локального поиска для kSAT]]
* ''[[Деревья Штейнера]]


== Литература ==
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)