35. Approximation Algorithms

많은 중요한 문제들은 NP-완전인데, 이 장에서는 이 문제들에 대한 다항 시간 근사 알고리즘을 다룬다.

Performance ratios for approximation algorithms

최적화 문제를 다룬다고 하자. 이 때 근사 알고리즘으로 얻은 해의 비용과 정확한 알고리즘으로 얻은 해의 비용의 비율이 ρ(n) 안쪽이면 근사 비율 ρ(n)을 가지며 이 알고리즘을 ρ(n)-근사 알고리즘이라 한다. 근사 비율은 1보다 작을 수 없으며, ρ(n) = 1이면 정확한 알고리즘이다. 많은 문제에 대해서는 다항 시간 작은 상수값 근사 알고리즘이 존재한다. 어떤 NP-완전 알고리즘은 근사 알고리즘에 시간을 더 많이 쓸 수록 더 좋은 근사율이 나오기도 한다. 최적화 문제의 근사 방식은 문제 인스턴스와 ε > 0을 받는 (1 + ε)-근사 알고리즘이다. 모든 ε에 대해 다항 시간이 된다면 이를 다항 시간 근사 알고리즘이라 한다. ε가 감소함에 따라 다항 시간 근사 방식의 수행 시간은 빠르게 증가할 수 있다. 근사 방식의 수행 시간이 1/ε와 n의 다항식일 때 완전 다항 시간 근사 방식이라 한다.

Chapter outline

이 장에서는 다항 시간 근사 알고리즘들을 다룬다.

35.1. The vertex-cover problem

비방향그래프의 정점 덮개는 (u, v) ∈ E이면 u ∈ V’ 또는 v ∈ V’가 되는 V’ ⊆ V이다. 정점 덮개의 크기는 정점 수이다. 정점 덮개 문제는 주어진 그래프의 최소 크기 정점 덮개인 최적 정점 덮개를 찾는 문제이다. 다음 알고리즘은 효과적인 근사 알고리즘이다.

APPROX-VERTEX-COVER(G)
C = Φ
E' = G.E
while E' ≠ Φ
    let (u, v) be an arbitrary edge of E'
    C = C ∪ {u, v}
    remove from E' every edge incident on either u or v
return C

Theorem. APPROX-VERTEX-COVER는 다항 시간 2-근사 알고리즘이다.

이의 4번째 줄이 선택하는 간선의 집합은 사실 그래프 G의 최대 매칭이다.

35.2. The traveling-salesman problem

여행 외판원 문제는 외판원이 도시들을 한 번씩만 순회할 때 간선으로부터 발생하는 비용의 합을 최소화시키는 문제이다. 많은 실용적 문제에서 u에서 w로 가는 가장 비용이 덜한 방법은 직접 가는 방법이다. 이 특성을 삼각 부등식이라 하며 c(u, w) ≤ c(u, v) + c(v, w)로 나타낸다. 여행 외판원 문제는 삼각 부등식을 만족하더라도 NP-완전이다. 여기서는 삼각 부등식인 경우에 대해 2-근사 알고리즘을 다룬다.

35.2.1. The traveling-salesman problem with the triangle inequality

이 경우의 근사 알고리즘은 다음과 같다.

APPROX-TSP-TOUR(G, c)
select a vertex r ∈ G.V to be a "root" vertex
compute a minimum spanning tree T for G from root r using MST-PRIM(G, c, r)
let H be a list of vertices, ordered according to when they are first visited in a preorder tree walk of T
return the hamiltonian cycle H

MST-PRIM의 간단한 구현으로도 이의 수행 시간은 \Theta(V^{2})이다.

Theorem. 삼각 부등식을 만족하는 여행 외판원 문제에서 APPROX-TSP-TOUR는 2-근사 알고리즘이다.

이는 전체 순회와 비교해 증명한다. 사실 이는 실용적으로 그리 좋은 선택은 아니다.

35.2.2. The general traveling-salesman problem

Theorem. P ≠ NP라면, 임의의 상수 ρ ≥ 1에 대해, 일반적인 여행 외판원 문제에 대한 ρ-근사 다항 시간 알고리즘은 존재하지 않는다.

35.3. The set-covering problem

집합 덮개 문제는 자원들이 할당되어야 하는 문제를 모델링하는 최적화 문제이다. 이는 NP-난해이다. 구체적으로, 집합-덮개 문제의 인스턴스 (X, \mathcal{F})는 유한집합 X와 X의 부분집합의 집합 \mathcal{F}로, X의 임의의 원소가 \mathcal{F} 내의 부분집합 중 하나에는 속하는 것이다. 이 때 X = \cup_{S \in \mathcal{F}} S이면 S \in \mathcal{F}가 그 원소를 덮는다고 한다. 문제는 X 전체를 덮는 최소 크기 부분집합 \mathcal{C} \subseteq \mathcal{F} 를 찾는 것이다. 즉, X = \cup_{S \in \mathcal{C}} S가 되게 하는 \mathcal{C}를 찾는 것이다.

A greedy approximation algorithm

탐욕적 근사 알고리즘은 다음과 같다.

GREEDY-SET-COVER(X, F)
U = X
C = Φ
while U ≠ Φ
    select an S ∈ F that maximizes |S ∩ U|
    U = U - S
    C = C ∪ {S}
return C

간단한 구현은 O(\lvert X \rvert \lvert \mathcal{F} \rvert \min (\lvert X \rvert ,\lvert \mathcal{F} \rvert))이다. 선형 시간 구현도 가능하다.

Analysis

Theorem. GREEDY-SET-COVER는 다항 시간 ρ(n)-근사 알고리즘으로, \rho(n) = H(\max \{\lvert S \rvert : S \in \mathcal{F} \}) 이다.

Corollary. GREEDY-SET-COVER는 다항 시간 (\ln \lvert X \rvert + 1)-근사 알고리즘이다.

35.4. Randomization and linear programming

근사 알고리즘을 고안하는 데 있어 중요한 2가지 기법인 무작위화와 선형 계획법을 알아보자.

A randomized approximation algorithm for MAX-3-CNF satisfiability

최적화 문제를 다룬다고 하자. 이 때 무작위 근사 알고리즘으로 얻은 해의 기대 비용과 정확한 알고리즘으로 얻은 해의 비용의 비율이 ρ(n) 안쪽이면 근사 비율 ρ(n)을 가지며 이 알고리즘을 무작위 ρ(n)-근사 알고리즘이라 한다. 3-CNF 만족 가능성 문제로부터 유도되는 문제로 최대한 많은 절을 만족시키는 변수 세팅을 찾는 문제를 MAX-3-CNF 만족가능성 문제라 하자.

Theorem. n개의 변수와 m개의 절이 주어진 MAX-3-CNF 만족가능성 인스턴스에 대해, 각 변수를 1/2 확률로 1, 1/2 확률로 0으로 세팅하는 무작위 알고리즘은 무작위 8/7-근사 알고리즘이다.

Approximating weighted vertex cover using linear programming

최소 가중치 정점 덮개 문제에서는 그래프의 각 정점에 양의 가중치를 두고 최소 가중치의 정점 덮개를 찾는다. 비가중그래프에서 썼던 방법은 쓸 수 없다. 그 대신에 선형 계획법을 이용해 하한을 계산하고 이를 반올림해 정점 덮개를 찾는다. 최소 가중치 정점 덮개를 다음의 0-1 정수 계획법으로 볼 수 있다:

\sum_{v \in V}w(v) x(v)(u, v) \in E에 대해 x(u) + x(v) \geq 1, v \in V에 대해 x(v) \in \{0, 1\}에 대해 최소화.

이는 NP-난해이기 때문에 이를 완화한 다음의 선형 계획법 완화를 생각할 수 있다.

\sum_{v \in V}w(v) x(v)(u, v) \in E에 대해 x(u) + x(v) \geq 1, v \in V에 대해 x(v) \in [0, 1]에 대해 최소화.

아래 알고리즘은 선형 계획법 완화의 해를 이용해 0-1 정수 계획법의 해를 근사한다.

APPROX-MIN-WEIGHT-VC(G, w)
C = Φ
compute x', an optimal solution to the linear program
for each v ∈ V
    if x'(v) ≥ 1/2
        C = C ∪ {v}
return C

Theorem. APPROX-MIN-WEIGHT-VC는 최소 가중치 정점 덮개 문제에 대한 2-근사 다항 시간 알고리즘이다.

35.5. The subset-sum problem

부분집합-합 문제는 NP-완전이지만, 여러 쓸모가 있다.

An exponential-time exact algorithm

정확한 알고리즘은 다음과 같다. 지수 시간이다.

EXACT-SUBSET-SUM(S, t)
n = |S|
L_0 = <0>
for i = 1 to n
    L_i = MERGE-LISTS(L_(i-1), L_(i-1) + x_i)
    remove from L_i every element that is greater than t
return the largest element in L_n

A fully polynomial-time approximation scheme

이에 대한 근사 알고리즘은 각 목록이 생성된 뒤에 이를 잘라내서 이루어진다. 이는 다음과 같다.

TRIM(L, δ)
let m be the length of L
L' = <y_1>
last = y_1
for i = 2 to m
    if y_i > last * (1 + δ) // y_i ≥ last because L is sorted
        append y_i onto the end of L'
        last = y_i
return L'
APPROX-SUBSET-SUM(S, t, ε)
n = |S|
L_0 = <0>
for i = 1 to n
    L_i = MERGE-LISTS(L_(i-1), L_(i-1) + x_i)
    L_i = TRIM(L_i, ε/2n)
    remove from L_i every element that is greater than t
let z* be the largest value in L_n
return z*

Theorem. APPROX-SUBSET-SUM은 부분집합-합 문제의 완전 다항 시간 근사 방식이다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중