이번에 다룰 주제는 \(k\)-center problem입니다. 이 문제는 입력된 자료들을 몇 개의 덩어리로 묶음을 짓는 군집화(clustering) 문제 중 하나입니다. 군집화를 할 때 사용하는 상황이나 목적에 따라 어떤 군집이 좋고 나쁜지를 판가름하는 척도가 달라지게 될 것입니다. 이 문제의 목표는 최대한 공정하게 덩어리 짓는 방법을 찾는 것입니다. 다음 예시를 통해서 이 문제의 목표가 무엇인지 자세히 살펴보도록 하죠.
들어가기
자, 여러분이 회사를 하나 경영하고 있다고 하죠. 회사가 규모가 커서 다음 그림처럼 곳곳에 지부가 있다고 합시다.
이번에 사업을 확장하게되어 고가의 장비를 들여오게 되었습니다. 이 장비는 모든 지부의 부서들이 이용할 만큼 매우 요긴한 것이죠. 다만, 하도 가격이 비싸다보니 모든 지부에 하나씩 설치를 할 수 없어서 대신 장비를 설치할 지부를 세 곳 이하로 선정하기로 하였습니다. 문제는 그렇게 되면서 장비가 설치되지 않은 지부의 사람들이 장비가 설치된 지부로 출장을 가야 된다는 것입니다. 어떻게 하면 최대한 공정하게 장비를 설치할 수 있을까요?
예를 들어 장비를 다음과 같이 설치하였다고 가정해 보겠습니다.
그러면 장비가 설치되지 않은 지부의 사람들의 출장 거리는 다음 그림처럼 나타낼 수 있을 것입니다.
다음 그림은 이 중에서 가장 거리가 긴 것을 나타낸 것입니다. 그 말인 즉슨, 장비가 없는 지부의 사람들이 아무리 길어도 그 거리를 넘지 않고 출장을 갔다올 수 있다는 의미가 됩니다.
만약에 이를 고려하지 않고 맘대로 지부를 선정하게 되면 어떤 문제가 발생할까요? 다음 그림과 같이 선정했다고 생각해 봅시다.
그러면 장비가 없는 지부는 다음 그림에서 나타난 거리만큼 출장을 다녀와야 합니다.
다음 그림은 이 중 가장 거리가 긴 것을 나타낸 것입니다. 이렇게 선정하게 되면 동쪽 지부의 직원들의 불만을 크게 감수해야 할 것입니다.
따라서 장비를 설치할 지부를 선정하는 공정한 방식 중 하나는 최악의 경우를 최소화하는 것입니다. 분명 어떤 지부는 장비가 없어서 매우 먼 길을 왔다 갔다 해야할 겁니다. 이때, 가장 긴 출장길을 최대한 짧게 만들도록 지부를 선택한다면 모든 지부의 출장길이 이보다는 짧아진다는 것을 보장할 수 있습니다. 그러니 어떤 지부는 매우 가깝고 어떤 지부는 매우 멀리 있는 상황을 피할 수 있다는 것이죠. 이것이 바로 이번에 우리가 함께 고민하고자 하는 문제입니다.
문제 정의
위에서 제시된 상황을 수학적으로 나타내면 다음과 같습니다. 장비를 설치하고자 하는 \(n\) 곳의 지부 \(V\)와 임의의 두 지부 \(u, v \in V\) 사이의 거리 \(d(u, v)\)가 주어집니다. 우리의 목표는 지부를 최대 \(k\)개1 선정해서 각 지부와 거기에서 가장 가까운 선정된 지부 사이의 거리가 최소화되도록 하는 것입니다. 이때, 선정된 지부의 집합 \(S\)가 정해지면 각 지부 \(v\)에서 가장 가까운 선정된 지부도 함께 결정되므로 이를
\[d(S, v) := \min_{u \in S} d(u, v) \]
로 부르겠습니다. 우리의 목표는 \( d(S, v) \) 중에서 가장 길이가 긴 값을 최소화시키는 것입니다. 즉, \( |S| \leq k\)이면서
\[ \tau_S := \max_{v \in V} d(S, v) \]
가 가장 작은 \(S \subseteq V\)를 구하는 것이 목표인 것이죠. 이 문제가 바로 \(k\)-center problem입니다.
\(k\)-center problem
지점의 집합 \(V\)와 거리 \(d: V \times V \rightarrow \mathbb{Q}_{\geq 0} \) 그리고 자연수 \(k\)가 주어졌을 때, \(|S| \leq k\)이면서
\[ \tau_S := \max_{ v \in V} d(S, v) \]
를 최소화하는 \(S \subseteq V \)를 찾으시오.
이제부터 어떤 solution \(S\)가 주어졌을 때 정해지는 우리가 최소화해야 하는 값을 \( \tau_S \)라고 하겠습니다. 또한, 이 입력에서의 진짜 최적값을 \( \tau^\star \)라고 부르도록 하겠습니다.
Inapproximability
아쉽지만, 근사 알고리즘으로는 아무런 조건이 없는 \(k\)-center problem을 해결하기 쉽지 않습니다. 바로 다음에 소개할 문제 때문인데요. 그래프 \(G = (V, E)\) 하나가 주어졌을 때, 어떤 정점이 \(S\)에 포함되지 않으면 그것에 인접한 정점 중 최소 하나는 \(S\)에 포함되는 \(S \subseteq V\)를 dominating set이라고 부릅니다. 즉, 임의의 정점 \(v \in V\)에 대해서
- \(v \in S\)이거나
- \(u \in S\)이고 \( (u, v) \in E\)인 \(u\)가 존재하면
\(S\)를 dominating set이라고 합니다. 예를 들어, 다음 그림에서 빨간 정점은 dominating set입니다. 그래프의 모든 정점이 빨간 정점이거나 빨간 정점에 인접해 있기 때문이죠.
어떤 그래프가 주어졌을 때 크기가 큰 dominating set을 찾는 것은 매우 쉽습니다. 그냥 그래프의 모든 정점을 다 택하면 그만이니까요. 따라서 크기가 작은 것을 찾는 쪽이 흥미로운 방향입니다.
Dominating set problem
어떤 그래프 \(G = (V, E) \)와 자연수 \(k\)가 주어졌을 때, \(G\) 위에 크기가 \(k\) 이하인 dominating set이 존재하는지를 판별하시오.
왠지 그럴 것 같겠지만, 이 문제도 잘 알려진 \(\mathsf{NP}\)-complete 문제입니다.
이제 \(k\)-center problem을 근사적으로 해결하는 것은 쉽지 않다는 것을 보이도록 하겠습니다. 그 이유는 \(d\)에 아무런 조건이 없는 \(k\)-center problem을 해결하는 \(\rho\)-근사 알고리즘이 존재하면 상기한 dominating set problem을 해결할 수 있기 때문입니다.
Dominating set problem의 입력 \(G = (V, E) \)를 가지고 \(k\)-center problem의 입력을 다음과 같이 만들겠습니다. 먼저, 지점의 집합 \(V\)는 \(G\)의 정점의 집합 \(V\)를 그대로 가지고 옵니다. 거리 \(d : V \times V \rightarrow \mathbb{Q}_{\geq 0} \)는 다음과 같이 만듭니다.
\[ d(u, v) = \left\{ \begin{array}{ll} 0, & \text{if } u = v,\\ 0, & \text{if } (u, v) \in E, \\ 1, & \text{otherwise.} \end{array} \right. \]
만약 원래 문제의 입력에서 크기가 \(k\) 이하인 dominating set \( S^\star \)가 존재한다고 합시다. 이를 그대로 \(k\)-center problem의 입력에 가지고 오면 모든 지점 \(v\)에 대해 \( d(S^\star, v) = 0 \)이 된다는 사실을 알 수 있습니다. 바로 dominating set의 정의에 의해서 말이죠. 반대로 만들어진 \(k\)-center problem의 입력에 대해 \( \tau^\star = 0 \)이라면 똑같이 dominating set problem에서 크기가 \(k\) 이하인 dominating set을 얻을 수 있습니다. 원래 문제의 입력에 간선이 있는 경우에만 거리가 \(0\)이고 그렇지 않으면 \(1\)이기 때문에 앞에서 \( \tau^\star \)를 주는 solution을 그대로 가지고 오면 됩니다. 따라서 원래 문제의 입력에 크기가 \(k\) 이하인 dominating set이 존재할 필요충분조건은 만들어진 \(k\)-center problem의 입력의 최적값 \( \tau^\star\)가 \(0\)인 것입니다. 반대로, \( \tau^\star > 0\)이라면 원래 문제의 입력에는 원하는 답이 존재하지 않는다는 것이죠.
앞에서 \(k\)-center problem을 해결하는 \( \rho \)-근사 알고리즘이 존재한다는 것을 가정했습니다. 이는 만들어진 입력에서 \( \tau_S \leq \rho \cdot \tau^\star \)를 만족하는 \( S \)를 반환할 것입니다. 요는 \(0\)에 어떤 값 \( \rho < \infty \)를 곱해도 그대로 \(0\)이 된다는 점입니다. 따라서 \( \tau^\star = 0\)이면 알고리즘은 \( \tau_S = 0 \)인 \(S\)를 반환할 것이며, 반대로 \( \tau^\star > 0\)이라면 \( \tau_S > 0\)이 될 것입니다.
이를 통해서 원래 문제의 입력에 크기가 \(k\)를 넘지 않는 dominating set이 존재하는지 여부를 판단할 수 있습니다. 만약 근사 알고리즘이 \(\tau_S = 0\)인 \(S\)를 반환한다면 원래 문제의 입력이 참이라는 뜻이고, 반대로 \(0\)보다 크다면 거짓이라는 뜻이기 때문이죠. 그러므로 \( \mathsf{P} \neq \mathsf{NP} \)인 이상에야 \(k\)-center problem을 해결하는 \(\rho\)-근사 알고리즘은 존재할 수 없게 됩니다.
Metric & hardness
위 증명에서 사용된 테크닉은 traveling salesman problem의 inapproximability를 증명할 때도 비슷하게 사용되었습니다.
[Traveling Salesman Problem] Metricity & 2-Approximation
안녕하세요. 이번에는 traveling salesman problem에 대해서 알아보도록 하겠습니다. 주로 줄여서 TSP라고도 부르며, 제가 알기로 우리말로는 외판원 문제로 불립니다. 개괄적인 설명은 이전 글에서 했습니다. 201..
gazelle-and-cs.tistory.com
근사 알고리즘으로는 일반적인 거리가 주어졌을 때 traveling salesman problem을 해결하기 쉽지 않아서 대신 우리는 입력에 약간의 조건을 주었습니다. 바로 거리가 metric이라는 점입니다. 거리 \(d\)가 \(V\) 위에서 metric이 되려면 임의의 \(u, v, w \in V\)에 대해서
- \( d(u,v) = 0 \Leftrightarrow u = v \),
- \( d(u,v) = d(v, u) \),
- \( d(u, v) \leq d(u, w) + d(w, v) \)
조건을 모두 만족해야 합니다.
일반적인 거리에 대해서는 근사 알고리즘을 만들 수 없었지만, 만약 \(d\)가 metric이라면 어떻게 될까요? TSP 때와 마찬가지로 좋은 근사 알고리즘을 얻을 수 있습니다. 이는 다음 포스트에서 다루어 보도록 하겠습니다. 대신 이번 시간에는 당연하게 넘어갔지만 사실은 증명이 필요한 부분을 생각해 보겠습니다. 바로 거리가 metric이 되었을 때에도 여전히 문제가 풀기 쉽지 않다는 것을 증명하는 것이죠.
이 말이 무슨 뜻인지 설명해 보겠습니다. 앞에서 일반적인 거리에 대해서 \(k\)-center를 풀자니 너무 어려워서 대신 거리를 metric으로 바꾸어 보았죠. 아무래도 일반적인 거리가 아니라 특수한 형태의 거리만을 입력으로 취하니 문제의 난이도는 낮아졌을 것입니다. 여기서 우려하는 것은 문제가 너무 쉬워지지는 않겠냐는 것입니다. 만약에 metric이 입력으로 주어지는 문제는 다항 시간에 해결이 가능하다면 굳이 근사 알고리즘을 만드는 수고를 들일 필요가 없어지는 것이죠.
다행(?)히도 난이도가 우려할 만큼 쉬워지지 않습니다. 입력이 metric인 경우에도 여전히 \(k\)-center는 \(\mathsf{NP}\)-hard 합니다. 증명은 간단합니다. 앞에서 사용한 dominating set problem을 이번에도 가지고 올 겁니다.2 똑같이 \(k\)-center problem의 입력을 만들 텐데, 거리 \(d\)가 다음과 같이 약간 달라지게 됩니다.
\[ d(u, v) = \left\{ \begin{array}{ll} 0, & \text{if } u = v,\\ 1, & \text{if } (u, v) \in E, \\ 2, & \text{otherwise.} \end{array} \right. \]
즉, \(0\) 대신에 \(1\), \(1\) 대신에 \(2\)를 넣는 것이죠. 이렇게 얻은 거리가 metric이라는 것은 쉽게 증명할 수 있습니다. 1번 조건과 2번 조건은 어렵지 않게 증명할 수 있습니다. 마지막으로 3번 조건은 거리가 아무리 길어도 \(2\)를 넘지 않는 반면, 아무리 짧아도 \(1\)보다는 짧아질 수 없기 때문에 성립하게 됩니다.
이제 입력이 metric인 \(k\)-center problem을 정확히 해결하는 알고리즘이 있다고 가정해 보겠습니다. 만약 \( \tau^\star \leq 1\)이라면 이는 원래 문제의 선택되지 않은 모든 정점이 간선을 통해 선택된 정점에 할당될 수 있다는 의미이므로 원래 문제에 원하는 dominating set이 존재한다는 의미입니다. 반대로 \( \tau^\star = 2 \)라면 원래 문제에 그러한 것이 존재하지 않는다는 것을 보여주죠. 따라서 metric \(k\)-center problem도 \(\mathsf{NP}\)-hard 하게 됩니다.3
마치며
이번에는 \(k\)-center problem에 대해서 알아 보았습니다. 이 문제는 어떻게 하면 여러 개체를 공정하게 덩어리 지을 수 있을지에 대하여 묻습니다. 안타깝게도 일반적인 거리가 입력 되었을 때는 이를 근사적으로 해결하기 쉽지 않다는 것을 증명하였습니다. 대신 거리가 metric으로 주어지는 경우에 대해서 고민하기로 했죠. 불행인지 다행인지 모르겠지만 거리가 metric이 되어도 문제가 여전히 어렵기는 마찬가지였습니다.
하지만 후자의 경우에는 좋은 근사 알고리즘을 구할 수 있습니다. 바로 근사비가 2인 알고리즘이죠. 처음 예시에 빗대어 설명하자면 장비가 설치되지 않은 지부에서 설치된 지부까지의 출장 거리의 최댓값이 최적값의 두 배를 넘지 않을 것이라는 겁니다. 놀라운 것은 2보다 좋은 근사비를 갖는 알고리즘은 존재하지 않는다는 것을 증명할 수 있다는 점입니다. 다음 포스트에서는 이에 대해서 자세히 다루어 보도록 하겠습니다.
읽어 주셔서 고맙습니다. :)
출처
1. 빌딩 아이콘 : Icon made by Payungkead from Flaticon
2. 장비 아이콘 : Icon made by srip from Flaticon
각주
1. 이 문제를 최대 \(k\)개 선택하는 것이 아닌 정확히 \(k\)개를 선택하는 문제로도 정의할 수 있습니다. 하지만 두 버전의 차이는 없습니다. 왜냐하면 한 버전을 풀 수 있으면 다른 버전도 풀 수 있기 때문입니다. 먼저 최대 \(k\)개를 선택하는 버전을 해결하는 알고리즘이 있다고 가정해 봅시다. 만약 반환된 결과가 \(k\)보다 적은 지점을 선정했다면, 아무 지점을 몇 개 더 선정하여 \(k\)를 맞추어 주면 됩니다. 그 이유는 지점을 더 선정한다고 최대 거리가 증가하지 않기 때문입니다. 반대로 정확히 \(k\)개를 선택하는 문제를 해결하는 알고리즘이 주어진 경우에는 \(1\)부터 \(k\)까지 모두 돌려본 후 그중 최대 거리가 최소가 되는 결과를 반환하면 됩니다. 어차피 \(k\)는 \(|V|\)를 넘을 수 없으므로 이 작업은 다항 시간에 끝납니다.
2. 어떤 문제가 \(\mathsf{NP}\)-hard 임을 증명하는 방식은 크게 두 가지가 있습니다. 첫 번째는 임의의 \( \mathsf{NP} \) 문제를 해당 문제를 통하여 해결할 수 있음을 증명하는 것이죠. 두 번째는 알려진 다른 \( \mathsf{NP} \)-hard한 문제를 가지고와서 원래 문제를 해결할 수 있으면 이 문제도 해결할 수 있다는 것을 증명하는 것입니다. 이 글에서 택한 방식은 후자입니다. 좀 더 엄밀히는, 어떤 \( \mathsf{NP} \)-hard 문제를 우리가 고려하는 문제로 polynomial-time reducible하다는 것을 증명하는 것입니다.
3. 동일한 방식으로 metric traveling salesman problem이 \( \mathsf{NP} \)-hard 하다는 것도 증명할 수 있습니다.
'근사 알고리즘 > Facility location' 카테고리의 다른 글
| 설비 입지 선정 원-쌍대 근사 알고리즘 (Primal-Dual Approximation Algorithm for Facility Location) (0) | 2024.01.27 |
|---|---|
| 설비 입지 선정 문제 (Facility Location Problem) (6) | 2022.10.03 |
| [k-Center Problem] 2-근사 알고리즘 (0) | 2019.09.24 |
