4446
правок
Аппроксимационные схемы для задач с планарными графами: различия между версиями
Материал из WEGA
Аппроксимационные схемы для задач с планарными графами (посмотреть исходный код)
Версия от 00:27, 20 апреля 2012
, 20 апреля 2012нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 27: | Строка 27: | ||
Большинство приложений алгоритма Бэйкер ограничивались задачами оптимизации, возникающими из «локальных» свойств (к примеру, определяемых логикой первого порядка). Интуитивно представляется, что подобные локальные свойства можно доказать при помощи локальной проверки ближайшего окружения константного размера. В работе [5] подход Бэйкер был обобщен, что дало в результате PTAS-схемы для нелокальных задач – в частности, для нахождения связного доминирующего множества. Для этого обобщения потребовалось применение двух различных техник. Первая из них заключается в использовании ε-доли аппроксимации с константным или даже логарифмическим коэффициентом исходной задачи в качестве основы для достижения нужного нелокального свойства. Вторая техника заключается в использовании подзадач, перекрывающихся на <math>\Theta </math>(log n) уровней, вместо принятых в подходе Бэйкер <math>\Theta </math>(1). | Большинство приложений алгоритма Бэйкер ограничивались задачами оптимизации, возникающими из «локальных» свойств (к примеру, определяемых логикой первого порядка). Интуитивно представляется, что подобные локальные свойства можно доказать при помощи локальной проверки ближайшего окружения константного размера. В работе [5] подход Бэйкер был обобщен, что дало в результате PTAS-схемы для нелокальных задач – в частности, для нахождения связного доминирующего множества. Для этого обобщения потребовалось применение двух различных техник. Первая из них заключается в использовании ε-доли аппроксимации с константным или даже логарифмическим коэффициентом исходной задачи в качестве основы для достижения нужного нелокального свойства. Вторая техника заключается в использовании подзадач, перекрывающихся на <math>\Theta </math>(log n) уровней, вместо принятых в подходе Бэйкер <math>\Theta </math>(1). | ||
Несмотря на успехи в применении подхода Бэйкер к большему кругу задач, алгоритмы на базе планарных сепараторов способны решать задачи и других типов. Однако у этого подхода есть другое ограничение: он лучше всего подходит для задач, у которых отношение размера оптимального решения к n составляет не меньше некоторого константного множителя. Для широкого круга задач это ограничение было успешно преодолено [5]; в частности, это касается применения схемы PTAS к множеству возвратных вершин, к которому ранее ни подход Бэйкер, ни алгоритм на базе планарных сепараторов не были применимы. Для этого выполняется равномерное разделение оптимального решения, а не целого графа, с использованием отношения между древесной шириной и размером оптимального решения для ограничения древесной ширины графа; в результате получается сепаратор размера O( | Несмотря на успехи в применении подхода Бэйкер к большему кругу задач, алгоритмы на базе планарных сепараторов способны решать задачи и других типов. Однако у этого подхода есть другое ограничение: он лучше всего подходит для задач, у которых отношение размера оптимального решения к n составляет не меньше некоторого константного множителя. Для широкого круга задач это ограничение было успешно преодолено [5]; в частности, это касается применения схемы PTAS к множеству возвратных вершин, к которому ранее ни подход Бэйкер, ни алгоритм на базе планарных сепараторов не были применимы. Для этого выполняется равномерное разделение оптимального решения, а не целого графа, с использованием отношения между древесной шириной и размером оптимального решения для ограничения древесной ширины графа; в результате получается сепаратор размера <math>O(\sqrt{OPT})</math> вместо сепаратора размера <math>O(\sqrt{n})</math>. Граница древесной ширины <math>O(\sqrt{OPT})</math> следует из теории двумерности, описанной во введении к статье [[двумерность]]. Мы можем разделить оптимальное решение на приблизительно равные фрагменты, даже не обладая знанием оптимального решения, посредством аппроксимаций с константным или даже логарифмическим коэффициентом. При рекурсивном вычислении фрагменты не будут иметь ограниченные размеры, но их древовидная ширина будет ограниченной, в силу чего для построения оптимальных решений могут применяться быстрые алгоритмы с фиксированными параметрами. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
