Анализ доминирования - Domination analysis

Анализ доминирования из алгоритм аппроксимации - способ оценки производительности, представленный Гловером и Пунненом в 1997 году. В отличие от классического коэффициент аппроксимации Анализ, который сравнивает численное качество вычисленного решения с качеством оптимального решения, анализ доминирования включает в себя изучение ранга вычисленного решения в отсортированном порядке всех возможных решений. В этом стиле анализа говорят, что алгоритм имеет число доминирования или же число господства K, если существует подмножество K различные решения проблемы, среди которых результат алгоритма является лучшим. Анализ доминирования также можно выразить с помощью коэффициент господства, которая представляет собой долю пространства решений, которая не лучше данного решения; это число всегда находится в интервале [0,1], причем большее число указывает на лучшее решение. Анализ доминирования чаще всего применяется к проблемам, для которых известно общее количество возможных решений и точное решение которых затруднительно.

Например, в Проблема коммивояжера, Существуют (п-1)! возможные решения для проблемного экземпляра с п города. Если можно показать, что алгоритм имеет число доминирования, близкое к (п-1) !, или, что то же самое, иметь коэффициент доминирования, близкий к 1, тогда его можно считать предпочтительным по сравнению с алгоритмом с меньшим числом доминирования.

Если можно качественно найти случайные выборки пространства решения проблемы, как в задаче коммивояжера, то для рандомизированный алгоритм чтобы найти решение, которое с высокой вероятностью имеет высокий коэффициент доминирования: просто создайте набор образцов и выберите из них лучшее решение. (См., Например, Орлин и Шарма.)

Число доминирования, описанное здесь, не следует путать с числом доминирования графа, которое относится к числу вершин в наименьшем доминирующий набор графа.

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

Известные результаты

В этом разделе содержится технический обзор известных результатов.

Крышка Vertex

 Неприблизимость. Пусть ε> 0. Если только P = NP, не существует полиномиального алгоритма для вершинного покрытия, для которого число доминирования больше 3 ^ ((n-n ^ ε) / 3).

Рюкзак

 Неприблизимость. Пусть ε> 0. Если P = NP, не существует полиномиального алгоритма для Ранца, в котором его доминирующее число больше 2 ^ (n-n ^ ε).

Максимальная удовлетворенность

TSP

Рекомендации

• Гловер Ф. и Пуннен А. П. (1997). «Задача коммивояжера: новые решаемые случаи и связи с развитием аппроксимационных алгоритмов». J. Oper. Res. Soc. 48 (5): 502–510. Дои:10.1057 / palgrave.jors.2600392.
• Гутин, Грегори и Йео, Андерс (2004). «Введение в анализ доминирования» (PDF). Оптимизация онлайн. Внешняя ссылка в | publisher = (помощь)
• Орлин, Джеймс Б. и Шарма, Душянт (2002). «Расширенное соседство: определение и характеристика» (PDF).