집합 커버(Set Cover) 문제

References

• Algorithms (Sanjoy Dasgupta)

Contents

• Set Cover (집합 커버) 문제
• Approximation Factor

---

(a) 11개의 마을 (b) 서로 30마일 이내의 마을들

위 이미지에서 점들은 마을을 표현합니다. 여기서 학교를 어디에 배치할 것인가 결정하는데, 두 가지 제한 사항이 있습니다. 각 학교는 마을 내에 위치해야 하고, 학교는 어떤 마을에서도 30마일보다 가까운 곳에 위치해야 합니다. 이 경우 필요한 학교의 최소 갯수는 몇 개 일까요?

 

이 문제는 전형적인 집합 커버(set cover) 문제입니다. 각 마을 x에 대해, $S_x$는 30마일 이내에 있는 마을들의 집합이라고 합시다. x에 있는 학교는 기본적으로 이 집합의 다른 마을들을 커버(cover)합니다. 이때 문제는 '얼마나 많은 집합 $S_x$가 있는가?' 입니다.

 

Set Cover의 입력과 출력은 다음과 같습니다.

• Input: 요소들 B의 집합. $S_1, \cdots, \S_m \subseteq B$
• Output: 합집합이 B가 되는 $S_i$의 선택

이 예제에서 B의 요소들은 마을들을 의미합니다. 그리고 이 문제는 다음과 같이 그리디한 방법으로 해결할 수 있습니다.

• B의 모든 요소들이 커버될 때까지 다음을 반복: 커버되지 않는 가장 많은 수의 요소들을 가진 $S_i$를 뽑는다.

이는 매우 자연적이면서 직관적입니다. 이 예제에서 무엇을 할 수 있는지 살펴보겠습니다.

마을 a에 첫 번째로 학교를 배치합니다. a 위치에 배치하는 것이 가장 많은 다른 마을들을 커버합니다. 그런 다음, c, j, 그리고 f나 g를 선택하여 3개의 학교를 더 선택하면, 총 4개의 학교를 선택하게 됩니다. 하지만 이 예제의 솔루션에는 b, e, j를 선택하면 총 3개의 학교를 선택하는 것이 있습니다. 즉, 그리디한 방법이 최적의 솔루션을 찾지 못하고 있습니다.

 

하지만 다행히 최적의 솔루션과 그리 멀지는 않습니다.

Claim: B가 n개의 요소들을 포함하고, 최적의 커버가 k개의 집합들로 구성된다고 가정하면, 그리디 알고리즘은 최대 $k\ln n$개의 집합들을 사용하게 될 것이다.

$n_t$는 그리디 알고리즘을 t번 반복 후에 아직까지 커버되지 않은 요소들의 개수라고 가정해봅시다. 남아 있는 요소들은 최적의 k개의 집합들에 의해 커버되기 때문에, 이들 중에는 적어도 $\frac{n_t}{k}$개의 요소를 갖는 어떤 집합이 되어야 합니다. 따라서 그리디 전략은 다음 공식을 보장합니다.

$$n_{t+1} \leq n_t - \frac{n_t}{k} = n_t (1 - \frac{1}{k})$$

여기서 위 식은 $n_t \leq n_0 (1 - \frac{1}{k})^t$임을 의미합니다.

그리고, 아래의 부등식을 통해서 최적해의 경계를 얻을 수 있습니다.

• 모든 x에 대해 $1-x \leq e^{-x}$이며, 필요충분 조건으로 x = 0이면 $1-x = e^{-x}$이다.

위 식은 아래의 그래프에 의해서 쉽게 증명됩니다.

따라서, 다음의 식이 만족합니다.

$$n_t \leq n_0(1-\frac{1}{k})^t < n_0 (e^{-\frac{1}{k}})^t = ne^{-\frac{1}{k}}$$

그러므로 $t = k\ln n$에서 $n_t$는 $ne^{-\ln n} = 1$보다 엄격하게 작으며, 이는 커버되어지는 요소가 하나도 남아 있지 않음을 의미합니다.

 

그리디 알고리즘의 솔루션과 최적해 간의 비율(ratio)은 입력에 따라 다르지만, 항상 $\ln n$보다는 작습니다. 그리고 이 비율이 $\ln n$과 매우 근접하는 특정 입력들이 존재합니다. 여기서 가장 큰 비율을 그리디 알고리즘의 근사 계수(approximation factor)라고 부릅니다.

 

개선의 여지가 많은 것처럼 보이지만, 사실 이와 같은 희망은 근거가 없습니다. 또한 알려진 복잡한 가정 하에서, 더 작은 근사 계수를 갖는 다항 시간 알고리즘이 없는 것으로 아마도 없을 것입니다.

 

이 문제는 단순히 결정하는 경우에는 NP-Complete, 최적해를 구하는 문제인 경우에는 NP-Hard에 속합니다.