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

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

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

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

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

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

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

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

Крышка вершины

 Inapproximability. Let ε > 0. Unless P=NP, there is no polynomial algorithm for Vertex Cover
 such that its domination number is greater than 3^((n-n^ε)/3).

Рюкзак

 Inapproximability. Let ε > 0. Unless P=NP, there is no polynomial algorithm for Knapsack
 such that its domination number is greater than 2^(n-n^ε).

Ссылки

• Гловер Ф. и Паннен А.П. (1997). «Задача коммивояжера: новые решаемые случаи и связь с разработкой алгоритмов аппроксимации». Дж. Опер. Рез. Соц . 48 (5): 502–510. дои : 10.1057/palgrave.jors.2600392 . S2CID   123498731 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
• Гутин, Грегори и Йео, Андерс (2004). «Введение в анализ доминирования» (PDF) . Оптимизация онлайн. {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )
• Орлин, Джеймс Б. и Шарма, Душьянт (2002). «Расширенное соседство: определение и характеристика» (PDF) . {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )