L-환산

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

 정의 
최적화 문제 와 각 문제의 비용 함수 에 대해서, 함수 와 양수 가 다음의 조건을 만족할 경우 를 A에서 B로의 L-환산이라고 정의한다.
 두 함수 는 다항 시간에 계산가능하다.
 문제 에 속하는 입력 에 대해, 는 문제 의 입력이다.
 문제 에 속하는 입력 의 해가 일 때, 는 문제 의 입력 에 해당하는 해이다.
 입력 에 대한 최적 비용이 일 때, 모든 에 대해 를 만족하는 양수 가 존재한다.
 입력 의 해가 일 때, 모든 에 대해 를 만족하는 양수 가 존재한다.

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

분류:근사 알고리즘