L-환산

틀:위키데이터 속성 추적 L-환산(틀:Lang, linear reduction)은 최적화 문제 간의 근사 비율을 선형 보존하는 환산이다. 여기에서 'L'의 의미는 선형(linear)을 가리킨다.

정의

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

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

L-환산이 존재할 경우, 만약 A에 대한 $ϵ$-근사 알고리즘이 존재한다면 그 알고리즘은 B에 대한 $\alpha \beta ϵ$-근사 알고리즘으로도 사용할 수 있다. 즉, B에 대한 다항 시간 근사 해법(PTAS)이 존재하게 된다.