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

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