L-환산 문서 원본 보기

{{위키데이터 속성 추적}}
'''L-환산'''({{lang|en|L-reduction}}, linear reduction)은 [[최적화 문제]] 간의 근사 비율을 선형 보존하는 [[환산 (복잡도)|환산]]이다. 여기에서 'L'의 의미는 선형(linear)을 가리킨다.

== 정의 ==
최적화 문제 <math>A, B</math>와 각 문제의 비용 함수 <math>c_A, c_B</math>에 대해서, 함수 <math>f, g</math>와 양수 <math>\alpha, \beta</math>가 다음의 조건을 만족할 경우 <math>(f, g, \alpha, \beta)</math>를 A에서 B로의 '''L-환산'''이라고 정의한다.
* 두 함수 <math>f, g</math>는 다항 시간에 계산가능하다.
* 문제 <math>A</math>에 속하는 입력 <math>x</math>에 대해, <math>f(x)</math>는 문제 <math>B</math>의 입력이다.
* 문제 <math>B</math>에 속하는 입력 <math>f(x)</math>의 해가 <math>y</math>일 때, <math>g(y)</math>는 문제 <math>A</math>의 입력 <math>x</math>에 해당하는 해이다.
* 입력 <math>x</math>에 대한 최적 비용이 <math>OPT_A(x)</math>일 때, 모든 <math>x</math>에 대해 <math>\mathrm{OPT_B}(f(x)) \le \alpha \mathrm{OPT_A}(x)</math>를 만족하는 양수 <math>\alpha</math>가 존재한다.
* 입력 <math>f(x)</math>의 해가 <math>y</math>일 때, 모든 <math>y</math>에 대해 <math>|\mathrm{OPT_A}(x)-c_A(g(y))| \le \beta |\mathrm{OPT_B}(f(x))-c_B(y)|</math>를 만족하는 양수 <math>\beta</math>가 존재한다.

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

{{전거 통제}}

[[분류:근사 알고리즘]]