Алгоритм аппроксимации

• Определение и свойства аппроксимации

  • Аппроксимация – это приближение к оптимальному решению задачи оптимизации. 
  • Алгоритм аппроксимации должен быть эффективным и иметь гарантированную производительность. 

• Структура алгоритмов аппроксимации

  • Задача оптимизации включает входные данные и множество решений. 
  • Алгоритм ищет наилучшее решение с заданной точностью. 
  • Для задачи минимизации гарантируется, что решение алгоритма не превышает оптимального решения более чем в определенное число раз. 
  • Для задачи максимизации гарантируется, что оптимальное решение не меньше решения алгоритма более чем в определенное число раз. 

• Гарантии производительности

  • Существуют алгоритмы с абсолютной и относительной гарантиями производительности. 
  • Алгоритмы с абсолютной гарантией производительности имеют верхнюю границу коэффициента аппроксимации. 
  • Алгоритмы с относительной гарантией производительности эквивалентны для задач максимизации. 

• Эпсилон-член и его значение

  • Эпсилон-член может появиться в алгоритмах аппроксимации из-за мультипликативной ошибки и постоянной ошибки. 
  • Для произвольного ϵ > 0 можно выбрать N, чтобы член k / OPT был меньше ϵ для всех n ≥ N. 

• Другие понятия и алгоритмы

  • Анализ доминирования рассматривает ранги решений, а не их абсолютные значения. 
  • PTAS – это алгоритмы аппроксимации с параметром коэффициента аппроксимации. 
  • Параметризованные алгоритмы аппроксимации выполняются за короткое время. 
  • APX – это класс задач, для которых существуют алгоритмы с постоянным коэффициентом аппроксимации. 

• Сокращение с сохранением аппроксимации

  • Существуют точные алгоритмы, которые могут быть использованы для улучшения результатов приближенных алгоритмов.