4446
правок
Остовное дерево с максимальным количеством листьев: различия между версиями
Перейти к навигации
Перейти к поиску
м
Остовное дерево с максимальным количеством листьев (посмотреть исходный код)
Версия от 13:58, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 43: | Строка 43: | ||
(в) Градиенты и правила преобразования для эвристик локального поиска. | (в) Градиенты и правила преобразования для эвристик локального поиска. | ||
(г) | (г) Аппроксимационные алгоритмы с полиномиальным временем выполнения и границы эффективности, доказанные систематическим образом. | ||
(д) Структура, используемая для решения других задач. | (д) Структура, используемая для решения других задач. | ||
| Строка 107: | Строка 107: | ||
'''Цель (г): алгоритмы | '''Цель (г): аппроксимационные алгоритмы с полиномиальным временем выполнения''' | ||
Теория использования экстремальных структур с полиномиальным временем выполнения напрямую приводит к получению алгоритма | Теория использования экстремальных структур с полиномиальным временем выполнения напрямую приводит к получению аппроксимационного алгоритма ОДМЛ с константным множителем и полиномиальным временем выполнения. Вначале выполним редукцию G при помощи правил кернелизации. Правила редукции сохраняют параметры аппроксимации. Возьмем любое дерево T (не обязательно остовное) в графе G. Если выполняются все утверждения касательно структуры, тогда (согласно рассуждениям граничной леммы) дерево T должно иметь не менее n/c листьев для c = 3,75. Таким образом, восстановив T с учетом произведенной редукции, получим c-аппроксимацию. | ||