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

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

'''Теорема 1. Если f – нормализованная, монотонно возрастающая, субмодулярная целочисленная функция, то жадный алгоритм B дает приближенное решение с коэффициентом аппроксимации <math>H( \gamma) \;</math> от оптимального, где <math>\gamma = max_{x \in E} f( \{ x \} )</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>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>. Следовательно, для того, чтобы выполнялось

 

 

 

 

 

 

(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>.

 

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

 

 

 

 

''Доказательство''. Поскольку все <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>.

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

 

 

Теперь можно провести корректный анализ жадного алгоритма 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>,

 

 

где <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>.

 

 

Выберем такое <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.

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

* ''[[Алгоритмы локального поиска для k-КНФ]]