4551
правка
Аппроксимационные схемы для задач с планарными графами: различия между версиями
Материал из WEGA
Аппроксимационные схемы для задач с планарными графами (посмотреть исходный код)
Версия от 00:13, 20 апреля 2012
, 20 апреля 2012→Постановка задачи
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
== Постановка задачи == | == Постановка задачи == | ||
Многие NP-полные графовые задачи проще решить при помощи аппроксимации на планарных графах и их обобщениях. (Граф является [[планарный граф|планарным]], если он может быть изображен на плоскости или сфере без пересечения дуг. Более подробно о других родственных классах графов см. [[двумерность]]). К примеру, в задаче нахождения [[максимальное независимое множество|максимального независимого множества]] нужно найти максимальное подмножество вершин графа, не порождающих дуг. Эта задача является неаппроксимируемой в графах общего вида с коэффициентом <math>n^{l- \epsilon}</math> для любого ε > 0, если только не окажется верным NP = ZPP (и неаппроксимируемой с коэффициентом <math>n^{l/2 - \epsilon}</math>, если только не окажется верным P = NP); в то же время для планарных графов можно выполнить 4-аппроксимацию (или простую 5-аппроксимацию), взяв наибольший цветовой класс для раскраски вершин в 4 цвета (или, соответственно, в 5 цветов). Другая задача – нахождение минимального доминирующего множества – заключается в поиске минимального подмножества вершин, такого, что каждая вершина либо входит в подмножество, либо смежна с ним; эта задача неаппроксимируема для графов общего вида с коэффициентом ε log n для некоторого ε > 0, если только не окажется верным P = NP, однако в случае планарных графов возможно применение полиномиальной схемы аппроксимации (PTAS) – набора алгоритмов аппроксимации с коэффициентами (1 + ε) для всех ε > 0. | Многие NP-полные графовые задачи проще решить при помощи аппроксимации на планарных графах и их обобщениях. (Граф является [[планарный граф|планарным]], если он может быть изображен на плоскости или сфере без пересечения дуг. Более подробно о других родственных классах графов см. [[двумерность]]). К примеру, в задаче нахождения [[максимальное независимое множество|максимального независимого множества]] нужно найти максимальное подмножество вершин графа, не порождающих дуг. Эта задача является неаппроксимируемой в графах общего вида с коэффициентом <math>n^{l- \epsilon}</math> для любого ε > 0, если только не окажется верным NP = ZPP (и неаппроксимируемой с коэффициентом <math>n^{l/2 - \epsilon}</math>, если только не окажется верным P = NP); в то же время для планарных графов можно выполнить 4-аппроксимацию (или простую 5-аппроксимацию), взяв наибольший цветовой класс для раскраски вершин в 4 цвета (или, соответственно, в 5 цветов). Другая задача – нахождение [[минимальное доминирующее множество|минимального доминирующего множества]] – заключается в поиске минимального подмножества вершин, такого, что каждая вершина либо входит в подмножество, либо смежна с ним; эта задача неаппроксимируема для графов общего вида с коэффициентом ε log n для некоторого ε > 0, если только не окажется верным P = NP, однако в случае планарных графов возможно применение [[полиномиальная аппроксимация|полиномиальной схемы аппроксимации]] (PTAS) – набора алгоритмов аппроксимации с коэффициентами (1 + ε) для всех ε > 0. | ||
Для построения PTAS-схем для планарных графов и их обобщений применяются два основных подхода: подход с использованием сепараторов и подход Бэйкер. | Для построения PTAS-схем для планарных графов и их обобщений применяются два основных подхода: подход с использованием сепараторов и подход Бэйкер. | ||
| Строка 8: | Строка 8: | ||
Подход с планарными сепараторами имеет два ограничения. Во-первых, он требует, чтобы отношение размера оптимального решения к n составляло не меньше некоторого константного множителя; в противном случае стоимость, внесенная сепараторами, может оказаться намного больше желаемого оптимального решения. Подобная граница может иметь место в некоторых задачах после усечения графа (нахождения ядра) – таких, как задача о независимом множестве, задача о вершинном покрытии и разные варианты задачи коммивояжера. Однако Гроу [12] утверждает, что для нахождения доминирующего множества «техники, основанные на теореме о сепараторах, неприменимы». Во-вторых, алгоритмы аппроксимации на основе планарных сепараторов часто оказываются непрактичными из-за больших константных множителей. Например, чтобы получить коэффициент аппроксимации 2, требуется произвести исчерпывающее решение для графов с 22400 вершинами. | Подход с планарными сепараторами имеет два ограничения. Во-первых, он требует, чтобы отношение размера оптимального решения к n составляло не меньше некоторого константного множителя; в противном случае стоимость, внесенная сепараторами, может оказаться намного больше желаемого оптимального решения. Подобная граница может иметь место в некоторых задачах после усечения графа (нахождения ядра) – таких, как задача о независимом множестве, задача о вершинном покрытии и разные варианты задачи коммивояжера. Однако Гроу [12] утверждает, что для нахождения доминирующего множества «техники, основанные на теореме о сепараторах, неприменимы». Во-вторых, алгоритмы аппроксимации на основе планарных сепараторов часто оказываются непрактичными из-за больших константных множителей. Например, чтобы получить коэффициент аппроксимации 2, требуется произвести исчерпывающее решение для графов с 22400 вершинами. | ||
Бэйкер [1] предложила подход, способный справиться со вторым ограничением; он до некоторой степени касается и первого ограничения. Этот подход основан на декомпозиции графа на перекрывающиеся подграфы с ограниченной внешнепланарностью. | Бэйкер [1] предложила подход, способный справиться со вторым ограничением; он до некоторой степени касается и первого ограничения. Этот подход основан на декомпозиции графа на перекрывающиеся подграфы с ограниченной внешнепланарностью. | ||
== Основные результаты == | == Основные результаты == | ||
