Остовное дерево с максимальным количеством листьев: различия между версиями

Цель (а): FPT-алгоритмы

Задача заключается в нахождении правил предварительной обработки (кернелизации) с полиномиальным временем выполнения, где g(k) насколько возможно мало. Это будет важно впоследствии в контексте цели (б).

Цель (б): предварительная обработка с полиномиальным временем выполнения и подпрограммы редукции данных

Ниже приводится пример таблицы, используемой для отслеживания каждого возможного состояния границы для возможного решения. Можно привести примеры, демонстрирующие исключительно успешное каскадное применение правил редукции к реальным распределениям данных и описывающие разнообразие математических феноменов, относящихся к правилам редукции. Например, некоторые правила редукции – такие как правило разложения на составляющие Клейнмана-Веста для задачи МЛОД (рис. 2) – имеют фиксированный «размер границы» (в данном случае равный 2), тогда как правила редукции типа «корона» не имеют такового.

Цель (в): градиенты и преобразования решений для локального поиска

Здесь приводится обобщение обычной формулировки для локального поиска, основанное на степени более сложного градиента в процессе получения более высоких границ кернелизации. Первая идея заключается в проведении локального поиска на основе поддержки «текущей структуры представления», а не полного решения (остовного дерева). Вторая идея состоит в использовании индуктивных приоритетов для определения градиента «лучшего решения» для локального поиска.