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

Материал из WEGA

Ключевые слова и синонимы

Техника анализа жадной аппроксимации


Постановка задачи

Рассмотрим граф 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]. Таким образом,


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.


См. также


Литература

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)