Введение

Доминирующий анализ алгоритма приближения — это способ оценки его эффективности, предложенный Гловером и Пунненом в 1997 году. В отличие от классического анализа коэффициента приближения, который сравнивает численное качество полученного решения с качеством оптимального решения, доминирующий анализ предполагает изучение ранга полученного решения в упорядоченном списке всех возможных решений. В рамках такого анализа, алгоритм характеризуется числом доминирования K, если существует подмножество из K различных решений задачи, среди которых выход алгоритма является наилучшим. Доминирующий анализ также может быть выражен через коэффициент доминирования, представляющий собой долю пространства решений, не превосходящую данное решение; это число всегда лежит в интервале [0, 1], при этом более высокие значения указывают на лучшие решения. Доминирующий анализ наиболее часто применяется к задачам, для которых известно общее число возможных решений и для которых получение точного решения затруднено. Например, в задаче коммивояжера для экземпляра с n городами существует (n-1)! возможных решений. Если удается показать, что алгоритм имеет число доминирования, близкое к (n-1)!, или, эквивалентно, коэффициент доминирования, близкий к 1, то его можно считать предпочтительнее алгоритма с меньшим числом доминирования. Если возможно эффективно получать случайные выборки из пространства решений задачи, как это происходит в задаче коммивояжера, то рандомизированному алгоритму легко найти решение, которое с высокой вероятностью будет обладать высоким коэффициентом доминирования: достаточно построить набор выборок и выбрать из них наилучшее решение. (См., например, Орлин и Шарма.) Следует отличать число доминирования, описанное здесь, от числа доминирования графа, которое обозначает количество вершин в наименьшем доминирующем множестве графа. В последнее время появляется все больше публикаций, в которых доминирующий анализ используется для оценки эффективности эвристических алгоритмов. Такой анализ можно рассматривать как альтернативу классической традиции анализа коэффициента приближения. Обе эти меры также могут рассматриваться как взаимодополняющие.

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

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

Вертикальная крышка

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

Оружие

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