다항시간 근사해법 PTAS

1 개요

polynomial-time approximation scheme (PTAS)

다항 시간 근사 해법

• 최적화 문제에 대한 근사 알고리즘의 한 종류
• 주로 NP-난해 문제에 적용됨
• 어떤 주어진 상수 [math]\displaystyle{ \epsilon\gt 0 }[/math]에 대해서, 최적해로부터 [math]\displaystyle{ \epsilon }[/math]배를 넘지 않는 해답을 찾아내는 알고리즘을 의미함

2 같이 보기

• 근사 알고리즘

3 참고

• 위키백과 "다항 시간 근사 해법"
• 다음백과 "다항시간 근사해법 PTAS"
• 네이버백과 "다항시간 근사해법 PTAS"