ТОЧКА ДОСТУПА

• Определение класса APX

  • APX – это класс NP задач оптимизации, решаемых с использованием алгоритмов аппроксимации с постоянным коэффициентом. 
  • Задачи в APX имеют эффективные алгоритмы, которые находят решение с точностью до фиксированного коэффициента. 

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

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

• Проблемы в APX

  • Проблемы в APX связаны с алгоритмами с постоянным коэффициентом аппроксимации. 
  • Если P = NP, то некоторые проблемы в APX не имеют PTAS, что делает их полными для APX. 

• Примеры задач в APX

  • MAX-3SAT-3 – это задача, в которой нужно найти максимальное количество предложений, выполнимых при однократном присвоении значений переменным. 
  • Другие примеры включают задачи упаковки в мусорные баки, минимальное покрытие вершины и минимальное доминирующее множество в графах. 

• Связанные классы сложности

  • PTAS – это класс задач, которые могут быть аппроксимированы с любой точностью за полиномиальное время. 
  • APX-промежуточные задачи находятся между PTAS и задачами в APX. 
  • Существуют также классы сложности 
  • f 
  • ( 
  • n 
  • ) 
  • APX, где 
  • это коэффициент аппроксимации. 

• Дополнительные сведения

  • Существуют также задачи, которые являются полными exp-APX, где коэффициент аппроксимации зависит от экспоненциального значения чисел в задаче. 
  • Для более детального изучения класса APX можно обратиться к литературе, указанной в конце статьи.