4430
правок
Жадные алгоритмы аппроксимации: различия между версиями
Материал из WEGA
Жадные алгоритмы аппроксимации (посмотреть исходный код)
Версия от 14:41, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 5 промежуточных версий этого же участника) | |||
| Строка 37: | Строка 37: | ||
Однако такой анализ является не вполне корректным. Далее будут рассмотрены некоторые конкретные вопросы и предложена новая общая техника анализа алгоритма | Однако такой анализ является не вполне корректным. Далее будут рассмотрены некоторые конкретные вопросы и предложена новая общая техника анализа жадного алгоритма аппроксимации с несубмодулярной гармонической функцией. | ||
== Основные результаты == | == Основные результаты == | ||
| Строка 180: | Строка 180: | ||
где <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>. | |||
f( | |||
opt | |||
g - i | Выберем такое <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. | |||
где | |||
== Применение == | == Применение == | ||
| Строка 195: | Строка 193: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Можно ли определить коэффициент эффективности 1 + H( | Можно ли определить коэффициент эффективности <math>1 + H( \delta) \;</math> для жадного алгоритма B в задаче MCDS? Ответ неизвестен. Неизвестно также, как получить четкое обобщение теоремы 1. | ||
== См. также == | == См. также == | ||
* ''[[Связное доминирующее множество]] | * ''[[Связное доминирующее множество]] | ||
* ''[[Алгоритмы локального поиска для | * ''[[Алгоритмы локального поиска для k-КНФ]] | ||
* ''[[Деревья Штейнера]] | * ''[[Деревья Штейнера]] | ||
== Литература == | == Литература == | ||
