여러 NP-Hard 문제에 근사 알고리즘을 사용할 수 있습니까?

Question

매핑을 통해 NP 하드 문제를 다른 NP 하드 문제로 줄일 수 있으므로 제 질문은 한 걸음 앞으로 다가갑니다. 예를 들어 그 모든 단계 : 다른 NP에도 매핑 할 수 있습니까? 사전에

감사 http://en.wikipedia.org/wiki/Approximation_algorithm에서

Answer 1

우리가

NP-어려운 문제가 approximability 매우 다양 것을 볼; 빈 패킹 문제와 같은 일부는 1보다 큰 인수 내에서 근사 될 수 있습니다 (이러한 근사 알고리즘 패밀리는 종종 다항식 시간 근사 체계 또는 PTAS라고 함). 최대 파벌 문제와 같이 P = NP가 아니면 다항식 요인이나 상수 내에서 근사하는 것은 불가능합니다. (끝 인용)

하나의 NP 완전 문제에서 양호한 근사가 다른 NP 완전 문제에서 좋은 근사는 아니다. 그 행운의 세계에서 NP 근사 문제는 거의 없기 때문에 쉽게 구할 수있는 NP 완전 문제를 사용하여 여기에 해당하지 않는 모든 NP 완전 문제에 대한 좋은 근사 알고리즘을 찾을 수 있습니다.

Answer 2

문제가 NP-Hard 인 것으로 밝혀지면 문제의 결정 버전을 고려합니다. 출력은 예 또는 아니요입니다. 그러나 근사 알고리즘을 고려할 때 문제의 최적화 버전을 고려합니다.

NP-Hard의 증명에서 감소를 사용하여 하나의 문제 근사 알고리즘을 사용하여 다른 문제를 해결하는 경우 근사 비율이 변경 될 수 있습니다. 예를 들어 문제 A에 대한 2 근사 알고리즘을 사용하여 문제 B를 해결하는 경우 문제 B에 대한 O (n) 근사 알고리즘을 얻을 수 있습니다. 이는 근사 비율을 유지하지 않기 때문입니다. 따라서 한 가지 문제에 대한 근사 알고리즘을 사용하여 다른 문제를 해결하려면 유용한 알고리즘을 얻으려면 그 감소가 근사 비율을 너무 많이 변경하지 않도록해야합니다. 예를 들어 L-reduction 또는 PTAS reduction을 사용할 수 있습니다.