Heuristic certificates via approximations

Предложен новый метод, в котором качество (необязательно оптимального) эвристического решения сертифицировано приближенным алгоритмом, а именно: результат эвристического решения сопровождается шкалой, получаемой из приближенного алгоритма. Создание шкалы эффективно, в то время как получение решения от алгоритма аппроксимации обычно требует длительных расчетов относительно эвристического подхода. С другой стороны, результаты, полученные с помощью эвристики без шкалы, могут быть бесполезными. Исследованы критерии для выбора схемы аппроксимации для получения шкалы. Чтобы получить шкалу на практике, приближения рассмотрены не только по их асимптотическому поведению, но также изучены соотношения между ними относительно размера ввода для данной проблемы. Для практического примера рассмотрены эвристические и приближенные алгоритмы для задач SINGLE KNAPSACK, MAX 3-SAT и MAXIMUM BOUNDED THREE-DIMENSIONAL MATCHING, которые являются известными NP-сложными задачами. Получены сертификаты для эвристических запусков с использованием подходящих приближений.