근사 보존 감소

계산가능성 이론과 계산 복잡성 이론, 특히 근사치 알고리즘의 연구에서 근사치 보존 감소는 최적으로부터의 해결책의 거리가 어느 정도 보존되도록 하나의 최적화 문제를 다른 문제로 변환하기 위한 알고리즘이다.근사치 보존 감소는 복잡성 이론의 더 일반적인 감소의 하위 집합이다. 차이점은 근사치 보존 감소는 의사결정 문제와 반대로 근사치 문제나 최적화 문제에 대한 진술을 한다는 것이다.

직관적으로, 문제 A와 문제 B에 대한 해결사(아마도 근사치)의 예를 들어, 문제 A를 문제 B의 인스턴스로 변환하고, 문제 B에 대한 해결사를 적용하고, A에 대한 해결책도 복구할 수 있다면, A는 근사치 보존을 통해 문제 B로 환원될 수 있다.근사치

정의

의사결정 문제의 감소와 달리 근사치 보존 감소는 한 문제에서 다른 문제로 축소할 때 문제 사례의 진실보다 더 많이 보존해야 한다.또한 두 문제 모두에서 최적의 비용에 대한 솔루션 비용 간의 관계에 대한 보증을 유지해야 한다.공식화하려면:

A와 B를 최적화 문제로 두자.

최적의 솔루션 ${\displaystyle \text{OPT}(x}$) ${\displaystyle {\text{}$와 함께 x를 문제 A의 인스턴스로 설정$OPT}}($${\displaystyle x}$$)\}.$ Let $c{\displaystyle {}_{}}$ ${\displaystyle A_{}}$( ${\displaystyle x}$, y${\displaystyle }$) ${\displaystyle c_{A}(x,y)}$은 문제 A의 인스턴스 x에 대한 솔루션 y의 비용을 나타낸다.이것은 또한 어떤 솔루션이 최적의 솔루션으로 간주되는지 결정하는 데 사용되는 메트릭이다.

근사 보존 감소는 기능 쌍$({\displaystyle f}$, ${\displaystyle g}$) ${\displaystyle (f,g)}($종종 다항식 시간에 계산할 수 있어야 함)이다.

• f는 A의 인스턴스 x를 B의 인스턴스$$ $x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ x$'}$에 매핑한다.
• g B의 솔루션$$ $y{\displaystyle {}^{}}$′ ${\$ y$'}$을(를) A의 솔루션 y에 매핑한다.
• g preserves some guarantee of the solution's performance, or approximation ratio, defined as ${\displaystyle R_{A}(x,y)=\max \left({\frac {c_{A}(x,{\text{$$OPT}(x)$$}}{c_{A}(x,y)}},{\frac {c_{A}(x,y)}{c_{A}(x,{\text}).$$OPT}(x)$$}}\오른쪽)}$ $."$

종류들

근사치 보존 감소에는 여러 가지 유형이 있는데, 모두 보증이 다르다(위 정의의 세 번째 지점).그러나 다른 감소와 달리 근사치 보존 감소는 최적화 문제(예: 복잡도 등급 멤버십 또는 완전성 또는 근사치)에 대해 그들이 입증하는 속성과 중복되는 경우가 많다.문제에 가장 쉽게 적응할 수 있는 적용 가능한 감소가 사용된다는 점에서 다른 유형의 감소가 대신 다양한 감소 기법으로 사용된다.

모든 근사치 보존 감소 유형을 모든 근사치 복잡성 등급의 멤버십을 보여주기 위해 사용할 수 있는 것은 아니며, 그 중 가장 주목할 만한 것은 PTAS와 APX이다.아래의 감소는 복잡도 등급 C의 멤버십을 유지하는데, A가 감소 방식을 통해 문제 B로 감소하는 문제, B가 C에 있다면 A도 C에 있는 것이다.아래에 표시된 일부 감소는 APX 또는 PTAS의 멤버십만 보존할 뿐 다른 멤버십은 보존하지 않는다.이 때문에, 특히 복잡성 등급 내에서 문제의 완전성을 증명하기 위한 목적으로 근사치 보존 감소를 선택할 때 신중한 선택을 해야 한다.

크레스켄지는 사용 편의성과 입증력 모두를 위해 가장 이상적인 세 가지 감소 스타일은 PTAS 감소, AP 감소, L 감소라고 제안한다.^[1]다음의 감소 설명은 근사치 보존 감소에 대한 크레스켄지의 조사에서 나온 것이다.

엄격한 감소

엄격한 감소는 근사치 보존 감소의 가장 단순한 유형이다.엄격한 감소에서 문제 B의 인스턴스 x에 대한 솔루션 y'의 근사비는 해당 솔루션 y와 문제 A의 인스턴스 x의 근사 비율만큼 좋아야 한다.즉, 다음과 같다.

${\displaystyle {}_{}}$$R$ ${\displaystyle A_{}}$( $x$${\displaystyle }$, $y$${\displaystyle }$) ${\displaystyle \le }$ ${\displaystyle R_{}}$ $B$( $x$$$, $y$ $′$${\displaystyle }$)${$ { { { { { { { { {${$ { \ = = ${\displaystyle =}$ = = ${\displaystyle =}$ = = = ${\displaystyle =}$ ${\displaystyle =}$ $=$ = =${\displaystyle {}^{}=}$ = = . $.$ . $.$ . . $..$

엄격한 감소가 가장 간단하다: 만약 A 문제에서 B 문제로의 엄격한 감소가 존재한다면, A 문제는 항상 B 문제만큼 좋은 비율에 근사치를 구할 수 있다.엄격한 감소는 PTAS와 APX의 멤버십을 보존한다.

${\displaystyle {유사}_{}}$한 ${\displaystyle \mathrm{S-축소}}$ 개념이 존재하며, 이에 대해 $c{\displaystyle {}_{}}$ A${\displaystyle {}_{}}$( ${\displaystyle {}^{}}$, ${\displaystyle {}^{}}$)${\displaystyle }$= ${\displaystyle c_{}}$ ${\displaystyle {}_{}}$( x ${\displaystyle {\prime }^{}}$, y ${\displaystyle {\prime }^{}}$) ${\displaystyle c_{A}(x,y)=c_{B}(x', y$ 그리고 두 해당 인스턴스들의 최적도 같은 비용을 가져야 한다.S-축소는 엄격한 축소의 매우 특별한 경우로, 훨씬 더 구속적이다.사실상 A와 B의 두 문제는 서로 거의 완벽하게 일치해야 한다.S-축소의 존재는 엄격한 축소의 존재뿐만 아니라 여기에 열거된 다른 모든 축소의 존재를 암시한다.

L-축소

L-축소는 APX뿐만 아니라 PTAS의 멤버십을 보존한다(단, 후자의 경우 최소화 문제만 해당).결과적으로 APX, Log-APX 또는 Poly-APX에 대한 완전성 결과를 입증하는 데 일반적으로 사용될 수 없지만, 그럼에도 불구하고 그것들은 자연적인 제형과 교정에서의 사용 편의성으로 평가된다.^[1]

PTAS 축소

PTAS 감축은 또 다른 일반적으로 사용되는 감축 방안이다.PTAS 회원권은 보존하지만 APX는 보존하지 않는다.그럼에도 불구하고 APX 완성도는 PTAS 감소 측면에서 정의된다.

PTAS-축소란 P-축소(P-Reducation)를 일반화한 것으로, 함수 g가 근사 비율 r에 의존할 수 있다는 차이만 있을 뿐이다.

A-축소 및 P-축소

감원과 P 감축은 각각 APX와 PTAS의 멤버십을 보여주기 위해 사용할 수 있는 유사한 감원 제도다.둘 다 계산 가능해야 하는 1보다 큰 숫자에 정의된 새로운 함수 c를 도입한다.

A-Reduction에서, 우리는 그것을 가지고 있다.

${\displaystyle R_{}}$ ${\displaystyle B_{}}$( ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$, y ${\displaystyle {\prime }^{}}$)${\displaystyle \le }$ ${\displaystyle r}$ → R ${\displaystyle A_{}}$( ${\displaystyle x}$, y${\displaystyle }$) ${\displaystyle \le }$ ${\displaystyle c}$( )${$ ${\displaystyle c}$ ( r ) {\$displaystyle R_{B}($x',$y')\leq r_{A}(x,$y)\leq c$(r$

P-축소로, 우리는 그것을 가지고 있다.

${\displaystyle {}_{}R}$ ${\displaystyle B_{}}$( ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$, y ${\displaystyle {\prime }^{}}$) ${\displaystyle \le }$ c${\displaystyle }$( ${\displaystyle r}$)${\displaystyle }$→ ${\displaystyle R_{}}$ ${\displaystyle {}_{}}$( ${\displaystyle x}$, y${\displaystyle }$) ${\displaystyle \le }$ r ${\displaystyle R_{B}(x',y')\leq c(r)\rightarrow R_{A}(x,y)\leq r}$.

P 감소의 존재는 PTAS 감소의 존재를 암시한다.

E-축소

엄격한 축소의 일반화지만 A축소와 P축소를 모두 내포하고 있는 E축소는 PTAS와 APX뿐만 아니라 Log-APX와 Poly-APX의 보다 큰 등급의 회원권을 보존하는 덜 제한적인 축소의 예다.E-축소에서는 다항식 p와 상수 $\beta {\displaystyle }$ ${\displaystyle \beta }$라는 두 가지 새로운 매개변수가 도입된다$.$ 그 정의는 다음과 같다.

E-축소에서는 다항식 p와 상수 $\beta {\displaystyle }$ ${\displaystyle \beta$ $\},$

• ${\displaystyle c_{B}({\text{})$$OPT}_{B}(x')\leq p( x )c_{A}({\text{}$$OPT}_{A}(x$ 여기서 ${\displaystyle x}$ $displaystyle$ x $}$은(는) 문제 인스턴스 설명 크기를 나타낸다.
• 솔루션 $y{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ y$'}$ to$$ B에 대해 우리는 $R{\displaystyle {}_{}}$ ${\displaystyle A_{}x{}^{}}$,${\displaystyle }$y${\displaystyle }$) ${\displaystyle \le }$ ${\displaystyle 1}$+ ${\displaystyle \beta }$ ${\displaystyle \cdot }$ ${\displaystyle (\mathrm{RB}{}_{}}$(${\displaystyle {}^{}}$ ,${\displaystyle {}^{}}$)${\displaystyle }$- 1${\displaystyle }$) ${\displaysty R_{A}(x,y)\leq 1+\beta$\cdot ($R_{B}(x,y$를 가지고 있다$.$

To obtain an A-reduction from an E-reduction, let ${\displaystyle c(r)=1+\beta \cdot (r-1)}$, and to obtain a P-reduction from an E-reduction, let ${\displaystyle c(r)=1+(r-1)/\beta }$.

AP 축소

AP 감소는 Log-APX 및 Poly-APX 클래스의 완전성을 정의하는 데 사용된다.PTAS 감축의 특별한 경우로서 다음과 같은 제한사항을 충족한다.

AP 감소에서는 일정 $\alpha {\displaystyle }$ ${\displaystyle \alpha$ $\},$

${\displaystyle R_{B}(x',y')\leq r\오른쪽 화살표 R_{A}(x,y)\leq 1+\alpha \cdot(r-1)}$

기능 g가 PTAS 감소에서와 같이 근사 비율 r에 의존할 수 있는 추가 일반화.

AP 감축도 E 축소의 일반화다.E-축소가 하는 것처럼, Log-APX와 Poly-APX 멤버십을 보존하기 위해 AP 축소에 실제로 추가 제한을 가해야 한다: 고정된 문제 크기의 경우, 근사비가 증가함에 따라 f, g의 계산 시간은 증가하지 않아야 한다.

격차감소

갭 감소는 일부 근사성 결과를 입증하는 데 유용하지만 여기에 표시된 다른 감소와 유사하지 않은 감소 유형이다.갭 감소는 문제 목표를 최적 솔루션과 최적 솔루션보다 더 나쁜 일부 곱셈 요인을 구별하도록 변경함으로써 발생하는 의사결정 문제 컨테이너 내의 최적화 문제를 다룬다.

참고 항목

• 감소(복잡성)
• PTAS 감소
• L-축소
• 근사 알고리즘

참조