Можно ли использовать алгоритм 1 аппроксимации для нескольких задач NP-Hard?

Question

Так как любая проблема NP Hard может быть сведена к любой другой проблеме NP Hard путем сопоставления, мой вопрос на 1 шаг вперед; например, каждый шаг этого алгоритма: может ли он быть сопоставлен с другим NP сложным?

заранее спасибо

Answer 1

При доказательстве проблемы NP-Hard мы обычно рассматриваем вариант решения проблемы, вывод которого либо да, либо нет. Однако при рассмотрении алгоритмов аппроксимации рассматривается вариант оптимизации задачи.

Если вы используете алгоритм аппроксимации одной задачи для решения другой задачи с помощью сокращения доказательства NP-Hard, коэффициент аппроксимации может измениться. Например, если у вас есть алгоритм 2-аппроксимации для задачи A, и вы используете его для решения задачи B, то вы можете получить алгоритм O(n)-приближений для задачи B, поскольку при сокращении не сохраняется коэффициент аппроксимации. Следовательно, если вы хотите использовать алгоритм аппроксимации для одной задачи для решения другой проблемы, вам нужно убедиться, что сокращение не изменит слишком сильно коэффициент аппроксимации, чтобы получить полезный алгоритм. Например, вы можете использовать L-сокращение или PTAS сокращение.

Answer 2

Из http://en.wikipedia.org/wiki/Approximation_algorithm мы видим, что

NP-сложные задачи сильно различаются по своей приближаемости; некоторые, такие как задача упаковки бинов, могут быть аппроксимированы в пределах любого фактора, превышающего 1 (такое семейство алгоритмов аппроксимации часто называют схемой аппроксимации полиномиального времени или PTAS). Другие невозможно аппроксимировать с помощью какой-либо постоянной или даже полиномиального фактора, если только P = NP, например, проблема максимальной клики. (конец цитаты)

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