Жадные алгоритмы аппроксимации
Ключевые слова и синонимы
Техника анализа жадной аппроксимации
Постановка задачи
Рассмотрим граф 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].
Проведем некоторый анализ вышеприведенного жадного алгоритма: Пусть x 1..: ; Xg – вершины, выбранные жадным алгоритмом в порядке их появления в алгоритме. Введем обозначение C, = {x\,... , x,}. Пусть C* = {y\,... , yopt} – минимальное связное доминирующее множество. Поскольку добавление C* к Ci уменьшит значение гармонической функции с f(Ci) до 2, значение f, уменьшенной на вершину из C*, будет в среднем составлять (f(Ci) — 2)/opt. Но, согласно жадному правилу выбора xi + 1, должно иметь место
Следовательно, 1 opt i+1 = {n-2) 1) opt
— opt
< (f(;) - где n = |V|. Заметим, что 1 - 1/ opt < е~11оР(. Следовательно, f(Ci)-2<(n-2)e-il°Pt : Выберем такое значение i, что f(Ci) > opt + 2 > f(Ci+1). Тогда opt < (п-2)е-"°Р( и g - i < opt :
Таким образом,
n-2"
opt
< opt + i < opt I 1 + ln
Однако такой анализ является не вполне корректным. Далее будут рассмотрены некоторые конкретные вопросы и предложена новая общая техника анализа алгоритма жадной аппроксимации с несубмодулярной гармонической функцией.
Основные результаты
Роль субмодулярности
Рассмотрим множество X и функцию f, определенную на множестве всех подмножеств 2X, то есть семействе всех подмножеств X. Функция f называется субмодулярной, если для любых двух подмножеств A и B в 2X выполняется
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).
Лемма 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 имеет место
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).
Доказательство. Заметим, что каждый связный компонент графа (v, D(B)) состоит из одного или нескольких связных компонентов графа (v, D(A)), поскольку A С B. Следовательно, количество связных компонентов (v, D(B)), доминируемых y, не превышает количества связных компонентов (v, D(A)), доминируемых y. Таким образом, лемма верна. Взаимоотношения между субмодулярными функциями и жадными алгоритмами рассматривались уже очень давно [3]. Пусть f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция. Рассмотрим задачу минимизации min c(A) при условии A 2 Cf :
где c – неотрицательная целевая функция, определенная на 2X, и Cf = fCj f(C [ fxg) - f(C) = 0 для всех x 2 Xg. Существует жадный алгоритм, вычисляющий приближенное решение этой задачи.
Жадный алгоритм B:
входные данные – субмодулярная функция f и целевая функция c;
while существует x 2 E, такое, что Axf(A) > 0
do выбрать вершину x, максимизирующую Axf(A)/c(x), и задать
A^AU {x}\ return A.
Следующие два результата хорошо известны.
Теорема 1. Если f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция, то жадный алгоритм B дает приближенное решение с коэффициентом аппроксимации H(y) от оптимального, где у = maxx2E f(fxg).
Теорема 2. Пусть f – нормализованная, монотонно возрастающая, субмодулярная функция, а c – неотрицательная целевая функция. Если в процессе выполнения жадного алгоритма B выбираемое значение x всегда удовлетворяет условию Axf(Aj-i)/c(x) > 1, тогда он дает приближенное решение с коэффициентом аппроксимации 1 + ln(/* /opt) от оптимального для вышеприведенной задачи минимизации, где f* = f(A*) и opt = c(A*) для оптимального решения A*.
Теперь вернемся к анализу жадного алгоритма A для MCDS. Кажется, что субмодулярность f в нем не используется. Однако на деле она используется в следующем утверждении:
«Поскольку добавление C* к Ci уменьшит значение гармонической функции с f(Ci) до 2, значение f, уменьшенной на вершину из C*, будет в среднем составлять (f(Ci) — 2)/opt. Но, согласно жадному правилу выбора xi + 1, должно иметь место
Чтобы убедиться в этом, рассмотрим утверждение более внимательно.
Пусть 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.
См. также
Литература
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)