L-환산

1. 개요

L-환산은 최적화 문제 A와 B 사이의 관계를 정의하는 개념으로, 문제 A의 입력과 해를 문제 B의 입력과 해로 변환하는 함수 f, g, 양수 α, β의 조건을 만족한다. L-환산이 존재하면 A에 대한 근사 알고리즘을 B에 대한 근사 알고리즘으로 사용할 수 있으며, 특히 B에 대한 PTAS가 존재하면 A도 PTAS를 갖는다. L-환산은 AP-환산 또는 PTAS 환산을 암시하며, P-환산을 함축한다. 지배 집합 및 토큰 재구성은 L-환산의 예시이다.

2. 정의

최적화 문제 $A,\; B$와 각 문제의 비용 함수 $c\_A,\; c\_B$에 대해서, 함수 $f,\; g$와 양수 $\backslash alpha,\; \backslash beta$가 다음의 조건을 만족할 경우 $(f,\; g,\; \backslash alpha,\; \backslash beta)$를 A에서 B로의 L-환산이라고 정의한다.

* 두 함수 $f,\; g$는 다항 시간에 계산가능하다.
* 문제 $A$에 속하는 입력 $x$에 대해, $f(x)$는 문제 $B$의 입력이다.
* 문제 $B$에 속하는 입력 $f(x)$의 해가 $y$일 때, $g(y)$는 문제 $A$의 입력 $x$에 해당하는 해이다.
* 입력 $x$에 대한 최적 비용이 $OPT\_A(x)$일 때, 모든 $x$에 대해 $\backslash mathrm\{OPT\_B\}(f(x))\; \backslash le\; \backslash alpha\; \backslash mathrm\{OPT\_A\}(x)$를 만족하는 양수 $\backslash alpha$가 존재한다.
* 입력 $f(x)$의 해가 $y$일 때, 모든 $y$에 대해 $|\backslash mathrm\{OPT\_A\}(x)-c\_A(g(y))|\; \backslash le\; \backslash beta\; |\backslash mathrm\{OPT\_B\}(f(x))-c\_B(y)|$를 만족하는 양수 $\backslash beta$가 존재한다.

L-환산이 존재할 경우, 만약 A에 대한 $\backslash epsilon$-근사 알고리즘이 존재한다면 그 알고리즘은 B에 대한 $\backslash alpha\backslash beta\backslash epsilon$-근사 알고리즘으로도 사용할 수 있다. 이는 B에 대한 다항 시간 근사 해법(PTAS)이 존재함을 의미할 수 있다.

3. 성질

(내용 없음)

3.1. PTAS 환산과의 관계

문제 A에서 문제 B로의 L-환산은 두 문제가 모두 최소화 문제일 경우에는 AP-환산을 암시하고, 두 문제가 모두 최대화 문제일 경우에는 PTAS 환산을 암시한다. 두 경우 모두, 만약 문제 B에 대한 PTAS(Polynomial-Time Approximation Scheme)가 존재하고 문제 A에서 문제 B로의 L-환산이 존재한다면, 문제 A에 대한 PTAS도 존재하게 된다.

이러한 성질 때문에 L-환산은 어떤 문제에 대한 PTAS 환산의 존재를 증명하는 대신 사용될 수 있다. 실제로 크레센지(Crescenzi)는 L-환산이 더 자연스러운 형태를 가지며 사용하기 쉽기 때문에 많은 경우에 더 유용하다고 주장했다.

3.1.1. 증명 (최소화 문제)

B의 근사율을 $1\; +\; \backslash delta$라고 가정한다.

A의 근사율 $\backslash frac\{c\_A(y)\}\{\backslash mathrm\{OPT\}\_A(x)\}$에서 증명을 시작한다.

문제 A와 B가 모두 최소화 문제이므로, L-환산 정의의 세 번째 조건에서 절댓값을 제거할 수 있다. 이 조건을 대입하면 다음과 같은 부등식을 얻는다.
: $\backslash frac\{c\_A(y)\}\{\backslash mathrm\{OPT\}\_A(x)\}\; \backslash le\; \backslash frac\{\backslash mathrm\{OPT\}\_A(x)\; +\; \backslash beta(c\_B(y\text{'})\; -\; \backslash mathrm\{OPT\}\_B(x\text{'}))\}\{\backslash mathrm\{OPT\}\_A(x)\}$

위 식을 단순화하고 L-환산 정의의 첫 번째 조건($\backslash mathrm\{OPT\}\_B(x\text{'})\; \backslash le\; \backslash alpha\; \backslash mathrm\{OPT\}\_A(x)$)을 적용하면 다음과 같다.
: $\backslash frac\{c\_A(y)\}\{\backslash mathrm\{OPT\}\_A(x)\}\; \backslash le\; 1\; +\; \backslash alpha\; \backslash beta\; \backslash left(\; \backslash frac\{c\_B(y\text{'})-\backslash mathrm\{OPT\}\_B(x\text{'})\}\{\backslash mathrm\{OPT\}\_B(x\text{'})\}\; \backslash right)$

여기서 괄호 안의 항 $\backslash left(\; \backslash frac\{c\_B(y\text{'})-\backslash mathrm\{OPT\}\_B(x\text{'})\}\{\backslash mathrm\{OPT\}\_B(x\text{'})\}\; \backslash right)$는 $\backslash frac\{c\_B(y\text{'})\}\{\backslash mathrm\{OPT\}\_B(x\text{'})\}\; -\; 1$과 같다. B의 근사율이 $1\; +\; \backslash delta$이므로, $\backslash frac\{c\_B(y\text{'})\}\{\backslash mathrm\{OPT\}\_B(x\text{'})\}\; \backslash le\; 1\; +\; \backslash delta$ 이다. 따라서 괄호 안의 항은 $\backslash delta$보다 작거나 같다. 이를 부등식에 적용하면 A의 근사율은 다음과 같이 제한된다.
: $\backslash frac\{c\_A(y)\}\{\backslash mathrm\{OPT\}\_A(x)\}\; \backslash le\; 1\; +\; \backslash alpha\backslash beta\backslash delta$

이는 A의 근사율이 $1\; +\; \backslash alpha\backslash beta\backslash delta$ 이하임을 의미하며, AP-환산의 조건을 만족한다.

3.1.2. 증명 (최대화 문제)

B의 근사율을 $\backslash frac\{1\}\{1\; -\; \backslash delta\text{'}\}$라고 하자.

A의 근사율, $\backslash frac\{c\_A(y)\}\{\backslash mathrm\{OPT\}\_A(x)\}$로 시작한다.

A와 B가 최대화 문제임을 알고 있으므로, L-환산 정의의 세 번째 조건 주변의 절댓값을 제거할 수 있다. 해당 조건을 대입하면 다음 부등식을 얻는다.

: $\backslash frac\{c\_A(y)\}\{\backslash mathrm\{OPT\}\_A(x)\}\; \backslash ge\; \backslash frac\{\backslash mathrm\{OPT\}\_A(x)\; -\; \backslash beta(c\_B(y\text{'})\; -\; \backslash mathrm\{OPT\}\_B(x\text{'}))\}\{\backslash mathrm\{OPT\}\_A(x)\}$

간소화하고 L-환산 정의의 첫 번째 조건을 대입하면, 다음을 얻는다.

: $\backslash frac\{c\_A(y)\}\{\backslash mathrm\{OPT\}\_A(x)\}\; \backslash ge\; 1\; -\; \backslash alpha\; \backslash beta\; \backslash left(\; \backslash frac\{c\_B(y\text{'})-\backslash mathrm\{OPT\}\_B(x\text{'})\}\{\backslash mathrm\{OPT\}\_B(x\text{'})\}\; \backslash right)$

괄호 안의 항은 $\backslash delta\text{'}$와 같으므로, A의 근사율은 $\backslash frac\{1\}\{1\; -\; \backslash alpha\backslash beta\backslash delta\text{'}\}$이다.

만약 $\backslash frac\{1\}\{1\; -\; \backslash alpha\backslash beta\backslash delta\text{'}\}\; =\; 1+\backslash epsilon$이면, $\backslash frac\{1\}\{1\; -\; \backslash delta\text{'}\}\; =\; 1\; +\; \backslash frac\{\backslash epsilon\}\{\backslash alpha\backslash beta(1+\backslash epsilon)\; -\; \backslash epsilon\}$가 된다. 이는 PTAS 환산 조건은 만족하지만 AP-환산 조건은 만족하지 않는다.

3.2. 기타 성질

L-환산은 다른 종류의 환산들과 중요한 관계를 맺고 있다.

L-환산은 P-환원을 함축하며, P-환원이 PTAS 환산을 함축하므로 L-환원 역시 PTAS 환원을 함축한다.

문제 A에서 문제 B로의 L-환산은 두 문제가 모두 최소화 문제일 경우에는 AP-환산을 암시하며, 두 문제가 모두 최대화 문제일 경우에는 PTAS 환산을 암시한다. 두 경우 모두, 만약 문제 B가 다항 시간 근사 해법(PTAS)을 가지고 있고 A에서 B로의 L-환산이 존재한다면, 문제 A 역시 PTAS를 갖게 된다. 이러한 성질 때문에 L-환산은 어떤 문제에 PTAS가 존재하는지 증명할 때, PTAS 환산의 존재를 직접 보이는 대신 사용될 수 있다. 크레센지(Crescenzi)는 L-환산이 더 자연스러운 형태를 가지며 사용하기 편리하여 실제 많은 경우에 더 유용하다고 제안하기도 했다.

또한, L-환원은 AP-환산을 함축하므로, 최소화 문제의 경우에만 APX 클래스의 멤버십을 보존한다. 즉, 최소화 문제 A가 APX에 속하고 A에서 다른 최소화 문제 B로의 L-환산이 존재한다면, B 역시 APX에 속하게 된다.

4. 예시

* 지배 집합: α = β = 1인 L-환산의 예시이다.
* 토큰 재구성: α = 1/5, β = 2인 L-환산의 예시이다.