맨위로가기

L-환산

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

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

더 읽어볼만한 페이지

  • 근사 알고리즘 - 최근접 이웃 탐색
    최근접 이웃 탐색은 다차원 공간에서 주어진 질의와 가장 유사한 데이터를 찾는 최적화 문제로, 데이터 압축, 데이터 마이닝, 기계 학습 등 다양한 분야에서 활용되며, 효율적인 탐색을 위해 다양한 알고리즘이 개발되고 있고, 개인 정보 보호 및 데이터 편향성과 같은 윤리적 문제에 대한 고려도 중요해지고 있다.
  • 근사 알고리즘 - 크리스토피데스 알고리즘
    크리스토피데스 알고리즘은 삼각 부등식을 만족하는 완전 그래프에서 외판원 문제의 근사해를 구하는 O(n3) 복잡도의 알고리즘으로, 최소 비용 신장 트리 생성, 홀수 차수 정점 집합 식별, 최소 가중치 완전 매칭 계산을 통해 해밀턴 회로를 구성하며 최적해의 3/2 이내의 근사 비율을 보장하고 다양한 분야에 응용된다.
L-환산
L-환산
L-reduction
종류틈새 감소
관련 항목계산 복잡도 이론

2. 정의

최적화 문제 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에 대한 최적 비용이 OPT_A(x)일 때, 모든 x에 대해 \mathrm{OPT_B}(f(x)) \le \alpha \mathrm{OPT_A}(x)를 만족하는 양수 \alpha가 존재한다.
  • 입력 f(x)의 해가 y일 때, 모든 y에 대해 |\mathrm{OPT_A}(x)-c_A(g(y))| \le \beta |\mathrm{OPT_B}(f(x))-c_B(y)|를 만족하는 양수 \beta가 존재한다.


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

3. 성질

(내용 없음)

3. 1. PTAS 환산과의 관계

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

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

3. 1. 1. 증명 (최소화 문제)

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

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

문제 A와 B가 모두 최소화 문제이므로, L-환산 정의의 세 번째 조건에서 절댓값을 제거할 수 있다. 이 조건을 대입하면 다음과 같은 부등식을 얻는다.

: \frac{c_A(y)}{\mathrm{OPT}_A(x)} \le \frac{\mathrm{OPT}_A(x) + \beta(c_B(y') - \mathrm{OPT}_B(x'))}{\mathrm{OPT}_A(x)}

위 식을 단순화하고 L-환산 정의의 첫 번째 조건(\mathrm{OPT}_B(x') \le \alpha \mathrm{OPT}_A(x))을 적용하면 다음과 같다.

: \frac{c_A(y)}{\mathrm{OPT}_A(x)} \le 1 + \alpha \beta \left( \frac{c_B(y')-\mathrm{OPT}_B(x')}{\mathrm{OPT}_B(x')} \right)

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

: \frac{c_A(y)}{\mathrm{OPT}_A(x)} \le 1 + \alpha\beta\delta

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

3. 1. 2. 증명 (최대화 문제)

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

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

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

: \frac{c_A(y)}{\mathrm{OPT}_A(x)} \ge \frac{\mathrm{OPT}_A(x) - \beta(c_B(y') - \mathrm{OPT}_B(x'))}{\mathrm{OPT}_A(x)}

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

: \frac{c_A(y)}{\mathrm{OPT}_A(x)} \ge 1 - \alpha \beta \left( \frac{c_B(y')-\mathrm{OPT}_B(x')}{\mathrm{OPT}_B(x')} \right)

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

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

3. 2. 기타 성질

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

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

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

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

4. 예시


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

참조

[1] 서적 On the Approximability of NP-complete \mathrm{OPT}imization Problems Royal Institute of Technology, Sweden
[2] 간행물 \mathrm{OPT}imization, Approximation, and Complexity Classes
[3] 서적 Proceedings of Computational Complexity. Twelfth Annual IEEE Conference IEEE Computer Society 1997


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com