4430
правок
Остовное дерево с максимальным количеством листьев: различия между версиями
Материал из WEGA
Остовное дерево с максимальным количеством листьев (посмотреть исходный код)
Версия от 12:58, 12 августа 2016
, 12 августа 2016нет описания правки
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 102: | Строка 102: | ||
Здесь приводится обобщение обычной формулировки для локального поиска, основанное на степени более сложного градиента в процессе получения более высоких границ кернелизации. Первая идея заключается в проведении локального поиска на основе поддержки «текущей структуры представления», а не полного решения (остовного дерева). Вторая идея состоит в использовании индуктивных приоритетов для определения градиента «лучшего решения» для локального поиска. | Здесь приводится обобщение обычной формулировки для локального поиска, основанное на степени более сложного градиента в процессе получения более высоких границ кернелизации. Первая идея заключается в проведении локального поиска на основе поддержки «текущей структуры представления», а не полного решения (остовного дерева). Вторая идея состоит в использовании индуктивных приоритетов для определения градиента «лучшего решения» для локального поиска. | ||
Цель (г): алгоритмы аппроксимации с полиномиальным временем выполнения | |||
Теория использования экстремальных структур с полиномиальным временем выполнения напрямую приводит к получению алгоритма аппроксимации МЛОД с константным множителем и p-кратным временем выполнения. Вначале выполним редукцию G при помощи правил кернелизации. Эти правила сохраняют параметры аппроксимации. Возьмем любое дерево T (не обязательно остовное) в G. Если выполняются все утверждения касательно структуры, тогда (согласно рассуждениям граничной леммы) дерево T должно иметь не менее n/c листьев для c = 3,75. Таким образом, восстановив T благодаря обращению редукции, получим c-вппроксимацию. | |||
Если по меньшей мере одно утверждение касательно структуры не выполняется, то дерево T можно улучшить, опираясь на один из индуктивных приоритетов. Заметим, что каждое утверждение доказано посредством рассуждения, которое можно интерпретировать как подпрограмму улучшения T с полиномиальным временем выполнения в случае противоречия утверждению. | |||
Последовательность этих действий можно применить к исходному дереву T (и его потомкам) только полиномиальное количество раз, определяемое списком индуктивных приоритетов, до того момента как мы получим дерево V, для которого выполняются все утверждения касательно структуры. В этот момент мы должны получить решение с c-аппроксимацией. | |||
