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

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

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

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

Рассмотрим граф 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.

См. также

• Связное доминирующее множество
• Алгоритмы локального поиска для k-КНФ
• Деревья Штейнера

Литература

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)