다항식 시간 근사 체계
컴퓨터 과학에서, 다항식 시간 근사 체계 (이하 PTAS 라 함)는 최적화 문제 (주로 NP 하드)에 대한 근사 알고리즘의 일종입니다.
PTAS는 최적화 문제의 인스턴스와 매개 변수 ε> 0을 입력으로 받아 다항식 시간 (1 - ε이 다) 내에 최적 해의 1 + ε 배 이하의 해를 구할 수있는 알고리즘입니다.
.
예를 들어, 유클리드 거리를 기반으로하는 여행 판매원 문제에서 최대 L (1 + ε) L의 솔루션을 찾을 수 있습니다.
여기서 L은 최적 솔루션의 길이입니다.
[1] PTAS의 실행 시간은 ε가 고정 될 때 문제의 크기 n의 다항식으로 결정되지만 ε에 대해서는 결정되지 않습니다.
따라서 실행 시간이 O (n1 / ε) 또는 O (nexp (1 / ε)) 인 경우에도 PTAS입니다.
변환
결정적인
PTAS 알고리즘의 실용적인 문제는 ε을 줄이면 다항식의 지수 부분이 크게 증가한다는 것입니다 (예 : O (n (1 / ε)!)).
이 문제를 다루는 한 가지 방법은 O (nc)를 효율적인 다항식 시간 근사 체계 (EPTAS)로 호출하는 것입니다.
여기서 실행 시간은 ε 알고리즘과 무관 한 상수로 c입니다.
이 경우 어떤 ε이 선택 되든 관계없이 문제의 크기는 실행 시간과 동일한 효과를 갖습니다.
그러나 O 표기법의 상수는 ε에 대해 임의로 커질 수 있습니다.
반면, 더 강한 제약 조건으로 실행 시간을 FPTAS (full polynomial-time approximation scheme)로서 문제 크기 n과 1 / ε의 다항식 시간이라고 부릅니다.
배낭 문제는 FPTAS 문제의 한 예입니다.
다항식으로 제한된 목적 함수를 사용하는 임의의 강도에 대한 NP- 하드 최적화 문제는 P = NP가 아니면 FPTAS를 가질 수 없습니다.
[2]
그러나 그 반대는 사실이 아닙니다.
예를 들어, P ≠ NP 일 때, 두 제약 조건을 갖는 배낭 문제는 FPTAS를 갖지 않지만, 목적 함수가 다항식으로 구속 되더라도, 그것은 강도가 높은 NP가 아니다.
[3] FPTAS ⊊ PTAS ⊊P = NP가 아니면 APX가 유지됩니다.
즉, 동일한 가정하에 APX 어려운 문제에는 PTAS가 없습니다.
또 다른 결정적인 PTAS 변형은 준 다항식 시간 근사 체계 (QPTAS)이다.
QPTAS는 고정 된 ε
엔
피
영형
엘
와이
엘
영형
지
(
엔
)
{\ displaystyle n ^ {폴리 로로그 (n)}}
시간 복잡성이 있습니다.
도적
PTAS가없는 문제는 PTAS와 유사한 특성을 갖는 다항식 시간 무작위 근사 체계 (PRAS)를 가질 수 있습니다.
PRAS는 최적화 문제의 인스턴스 인 다항식 시간 및 입력으로 매개 변수 ε> 0 인 높은 확률로 최적 해를 1 + ε 배 미만으로 해를 생성 할 수있는 알고리즘입니다.
높은 확률은 일반적으로 3/4 이상이지만, 대부분의 확률 론적 계산 복잡도 클래스는이 구체적인 값에 대해 견고합니다.
PTAS와 마찬가지로 PRAS는 문제 크기 n에 대해 다항식 계산 시간을 가져야하지만 ε에 대해서는 그렇지 않습니다.
우리는 ε에 대한 EPTAS와 동일한 제약 조건을 갖는 효율적인 다항식 시간 근사화 기법 (EPRAS)을 호출했다.
또한, FPTAS와 동일한 제약 조건을 갖는 것을 완전 다항식 시간 무작위 근사화 방정식 (FPRAS)이라고합니다.
[2]
참고 문헌
^ Sanjeev Arora, 유클리드 TSP 및 기타 기하학적 문제에 대한 다항식 시간 근사화, Journal of the ACM 45 (5) 753-782, 1998.
^ a b Vazirani, Vijay V.
(2003).
근사 알고리즘.
베를린 : 스프링 어.
pp.294-295.
ISBN 3-540-65367-8.
^ H.
Kellerer와 U.
Pferschy와 D.
Pisinger (2004).
배낭 문제.
뛰는 사람.
복잡성 동물원 : PTAS, EPTAS, FPTAS
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger, NP 최적화 문제 - 어떤 NP 최적화 문제에 PTAS가 있는지 나열하십시오.
"https://en.wikipedia.org/w/index.php?title= 다항식 시간 근사 방식 & oldid = 47465766"에서 가져옴
This article is taken from the Japanese Wikipedia
This article is distributed by cc-by-sa or GFDL license in accordance with the provisions of Wikipedia.
In addition, This site is simply not responsible for any show is only by translating the writings of foreign licenses that are compatible with CC-BY-SA license information.