Доминирование анализ из алгоритма аппроксимации является способом оценить его эффективность, введенный Гловер и Punnen в 1997 году В отличии от классического коэффициента аппроксимации анализа, который сравнивает численное качество расчетного раствора с тем из оптимального решения, анализ доминирования включает изучение ранг рассчитанного решения в отсортированном порядке всех возможных решений. В этом стиле анализа говорят, что алгоритм имеет число доминирования или число доминирования K , если существует подмножество из K различных решений проблемы, среди которых результат алгоритма является лучшим. Анализ доминирования также можно выразить с помощью коэффициента доминирования., которая представляет собой долю пространства решений, которая не лучше данного решения; это число всегда находится в интервале [0,1], причем большие числа указывают на лучшие решения. Анализ доминирования чаще всего применяется к проблемам, для которых известно общее количество возможных решений и точное решение которых затруднительно.
Например, в задаче коммивояжера ( n -1)! возможные решения для примера проблемы с n городами. Если можно показать, что алгоритм имеет число доминирования, близкое к ( n -1) !, или, что то же самое, имеет коэффициент доминирования, близкий к 1, то его можно считать предпочтительным по сравнению с алгоритмом с более низким числом доминирования.
Если возможно эффективно найти случайные выборки пространства решений проблемы, как в задаче коммивояжера, то рандомизированный алгоритм легко найдет решение, которое с высокой вероятностью имеет высокий коэффициент доминирования: просто создайте набор из образцы и выберите из них лучшее решение. (См., Например, Орлин и Шарма.)
Описанное здесь число доминирования не следует путать с числом доминирования графа, которое относится к числу вершин в наименьшем доминирующем множестве графа.
В последнее время появляется все больше статей, в которых анализ доминирования применяется для оценки эффективности эвристики. Этот вид анализа можно рассматривать как конкурирующий с традицией классического анализа отношения аппроксимации. Эти две меры можно также рассматривать как взаимодополняющие.
Известные результаты
В этом разделе содержится технический обзор известных результатов.
Крышка Vertex
Неприблизимость. Пусть ε> 0. Если P = NP , не существует полиномиального алгоритма для вершинного покрытия. такое, что его доминирующее число больше 3 ^ ((nn ^ ε) / 3).
Рюкзак
Неприблизимость. Пусть ε> 0. Если P = NP, для ранца не существует полиномиального алгоритма. такое, что его доминирующее число больше 2 ^ (nn ^ ε).
Максимальная удовлетворенность
TSP
Рекомендации
- Гловер, Ф. и Пуннен, А.П. (1997). «Задача коммивояжера: новые разрешимые случаи и связи с развитием аппроксимационных алгоритмов». J. Oper. Res. Soc . 48 (5): 502–510. DOI : 10,1057 / palgrave.jors.2600392 .CS1 maint: несколько имен: список авторов ( ссылка )
- Гутин, Грегори и Йео, Андерс (2004). «Введение в анализ доминирования» (PDF) . Оптимизация онлайн . Внешняя ссылка в
|publisher=
( помощь )CS1 maint: несколько имен: список авторов ( ссылка ) - Орлин, Джеймс Б. и Шарма, Душянт (2002). «Расширенное соседство: определение и характеристика» (PDF) .CS1 maint: несколько имен: список авторов ( ссылка )