다항식 시간 근사 체계

컴퓨터 과학에서 다항 시간 근사 체계(PTAS)는 최적화 문제(대부분 NP-하드 최적화 문제)에 대한 근사 알고리즘의 일종이다.

PTAS는 최적화 문제와 매개변수 ε > 0의 예를 들어 최적의 요인 1 + ε(또는 최대화 문제를 위한 1 - ε) 내에 있는 솔루션을 생성하는 알고리즘이다.예를 들어, 유클리드 여행 판매원 문제의 경우, PTAS는 최대 길이(1 + ε)L의 투어를 생산하며, L은 최단 투어의 길이가 된다.^[1]

PTAS의 가동 시간은 고정된 ε마다 문제 크기에서 다항식이어야 하지만 ε마다 다를 수 있다.따라서 시간 O(n^1/ε) 또는 심지어 O(n^exp(1/ε))로 실행되는 알고리즘은 PTAS로 계산된다.

변형

결정론적

PTAS 알고리즘의 실제적인 문제는 예를 들어 런타임이 O(n^(1/ε)!)인 경우 ε이 줄어들면서 다항식의 지수가 급격히 증가할 수 있다는 것이다.이를 해결하는 한 가지 방법은 효율적인 다항식 시간 근사 체계 또는 EPTAS를 정의하는 것이다. 이때 in과 독립적인 상수 c에 대해 가동 시간이 O(n^c)가 되어야 한다.이를 통해 문제 규모의 증가는 사용 중인 ε에 관계없이 런타임에 대해 동일한 상대적 영향을 미치지만, big-O 하의 상수는 여전히 ε에 임의로 의존할 수 있다.

훨씬 더 제한적이고 실제로 유용하게 사용되는 것은 완전 다항 시간 근사 체계 또는 FPTAS로, 알고리즘은 문제 크기 n과 1/2에서 모두 다항식이어야 한다.

P = NP가 아닌 한, FPTAS ⊊ PTAS ⊊ APX를 보유한다.^[2]따라서 이 가정 하에서 APX-하드 문제는 PTAS를 가지고 있지 않다.

PTAS의 또 다른 결정론적 변형은 준항명시간 근사 체계 또는 QPTAS이다.QPTAS는 고정된 각 $\varepsilon >0$ > $n^{\operatorname {polylog} (n)}$ ${\displaystyle$ $n^{\operatorname$ { $polylog}(n)}$ 에 대해 $n^{\operatorname {polylog} (n)}$ 시간 복잡성을 $n^{\operatorname {polylog} (n)}$ $\varepsilon >0$

무작위화

는 PTAS이 없으면 일부 문제. 그것은 최적화 또는 계수 문제이고 매개 변수 ε의 인스턴스를 이동하는 PRAS 있는 알고리즘, 0과, 다항 시간에 있는 높은 가능성이 있는 해결책을 생산하고 비슷한 속성을 임의적인 알고리즘, 다차 함수 시간 임의 추출된 근사 계획 또는 PRAS을 인정할 수 있다. 재치최적 요인 ε.일반적으로 "높은 확률"은 3/4보다 큰 확률을 의미하지만 대부분의 확률론적 복잡성 등급과 마찬가지로 정의는 정확한 값의 변동에 강하다(맨 최소 요구사항은 일반적으로 1/2보다 크다).Like a PTAS, a PRAS must have running time polynomial in n, but not necessarily in ε; with further restrictions on the running time in ε, one can define an efficient polynomial-time randomized approximation scheme or EPRAS similar to the EPTAS, and a fully polynomial-time randomized approximation scheme or FPRAS similar to the FPTAS.^[3]

복잡성 등급으로

PTAS라는 용어는 또한 PTAS가 있는 최적화 문제의 클래스를 가리키는 데 사용될 수 있다. PTAS는 APX의 하위 집합이며, P = NP가 아닌 한 엄격한 하위 집합이다.^[2]

PTAS 멤버십은 모두 PTAS 멤버십을 보존하는 PTAS 축소, L 축소 또는 P-축소를 이용하여 보여줄 수 있으며, PTAS 멤버십은 PTAS-완전성을 입증하는 데도 사용될 수 있다.한편, PTAS(이름, PTAS의 비회원성)에서 비회원성을 보여주는 것은 문제가 APX-hard임을 보여주는 것으로 이루어질 수 있으며, 그 후에 PTAS의 존재는 P = NP를 나타낼 것이다. APX-hardity는 PTAS 감소나 AP-축소를 통해 일반적으로 나타난다.

참고 항목

모든 밀집 제약 만족 문제(CSP) 클래스에 대한 PTAS가 존재한다.^[4]^{[clarification needed]}

참조

^ 산제프 아로라, 유클리드 TSP 및 기타 기하학적 문제에 대한 다항 시간 근사 체계, ACM 45(5) 753–782, 1998.
^ ^a ^b Jansen, Thomas (1998), "Introduction to the Theory of Complexity and Approximation Algorithms", in Mayr, Ernst W.; Prömel, Hans Jürgen; Steger, Angelika (eds.), Lectures on Proof Verification and Approximation Algorithms, Springer, pp. 5–28, doi:10.1007/BFb0053011, ISBN 9783540642015. 20페이지의 정의 1.30 다음에 나오는 토론을 참조하십시오.
^ Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8.
^ Arora, S.; Karger, D.; Karpinski, M. (1999), "Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems", Journal of Computer and System Sciences, 58 (1): 193–210, doi:10.1006/jcss.1998.1605

외부 링크

복잡성 동물원: PTAS, EPTAS.
Pierluigi Crescenzi, Viggo Kann, Magnous Halldorsson, Marek Karpinski 및 Gerhard Woeinger, NP 최적화 문제의 복합체 – 어떤 NP 최적화 문제가 PTAS에 있는지 나열한다.

[1] 산제프 아로라, 유클리드 TSP 및 기타 기하학적 문제에 대한 다항 시간 근사 체계, ACM 45(5) 753–782, 1998.

[Jansen-2] Jansen, Thomas (1998), "Introduction to the Theory of Complexity and Approximation Algorithms", in Mayr, Ernst W.; Prömel, Hans Jürgen; Steger, Angelika (eds.), Lectures on Proof Verification and Approximation Algorithms, Springer, pp. 5–28, doi:10.1007/BFb0053011, ISBN 9783540642015. 20페이지의 정의 1.30 다음에 나오는 토론을 참조하십시오.

[vvv-3] Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8.

[4] Arora, S.; Karger, D.; Karpinski, M. (1999), "Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems", Journal of Computer and System Sciences, 58 (1): 193–210, doi:10.1006/jcss.1998.1605

[1]

[2]

[3]

[4]

Search