[k-Center Problem] 2-근사 알고리즘

오랜만에 포스팅을 합니다. 아무래도 학기가 시작하니 글을 쓸 시간도, 마음도 나지 않는 것 같네요. 그래도 시작한 \(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\)를 찾으시오.

여기서, \(d(S,v)\)는 \(v\)에서 \(S\)의 어떤 지점까지의 거리 중 가장 가까운 것을 의미했습니다. 어떤 문제인지 잘 모르시면 이전 포스트를 참조하시기 바랍니다.

2019/08/16 - [근사 알고리즘/k-center problem] - [k-center problem] 문제 정의

[k-center problem] 문제 정의

이전 포스트에서 아무 \(d\)를 입력으로 받았을 때는 좋은 근사비를 얻기 어렵다는 것을 보였습니다. 대신, \(d\)에 약간의 조건을 붙였죠. 바로, \(d\)가 metric이라는 가정입니다. 하지만 여전히 metric \(k\)-center problem은 풀기 쉽지 않습니다. 지난 시간에 이 문제가 \(\mathsf{NP}\)-hard 하다는 것도 함께 보였습니다.

 

하지만 다행히도 \(d\)가 metric인 경우에는 근사비가 2인 괜찮은 근사 알고리즘을 얻을 수 있습니다.^[1] 이번 포스트에서는 그 알고리즘에 대해서 알아 보도록 하겠습니다. 참고로 다음 글도 metric \(k\)-center problem의 근사 알고리즘에 관한 글입니다.

https://kks227.blog.me/221245800064

k-center: Greedy

여기서는 제가 오늘 소개해 드릴 것과는 또다른 2-근사 알고리즘을 볼 수 있습니다. 매우 간단하면서도 재미있는 알고리즘이랍니다. 또한, metric \(k\)-center problem이 2보다 좋은 근사비를 가질 수 없다는 것도 함께 보입니다. 궁금하신 분들은 찾아가 보시면 좋겠네요. 특히 후자는 제가 소개해 드리지 않을 예정이니 읽어보시는 것을 추천드립니다.

Dominating set으로 환원하기

어떤 문제를 풀 때 우리가 자주 사용하는 기법 중 하나는 좀 더 다루기 쉬운 문제로 바꾸는 것입니다. 그러고 나서 원래 문제와 새로 정의한 문제 사이의 연관성을 따지는 것이죠. 이를 reduction이라고 합니다. 우리말로는 환원으로 번역이 됩니다. 사실 저는 환원이라는 표현이 그다지 와닿지는 않습니다. 대신 reduction의 의미를 따지자면 무언가를 제외한다, 축소시킨다는 뜻입니다. 즉, 원래의 복잡한 문제를 단순한 문제로 '축소'시켜서 우리가 다룰 수 있는 상태로 만들고, 답을 구하면 원래 문제의 답을 추출하는 것이죠.

 

지난 포스트에서 이 문제와 매우 깊은 연관성을 갖는 문제를 하나 정의하였습니다. 바로 dominating set problem인데요. 어떤 그래프 \(G = (V, E)\)가 주어졌을 때, 어떤 정점 집합 \(S \subseteq V\)에 어떤 정점 \(v\)가 속하지 않으면, 대신 \(v\)에 인접한 정점 중 하나가 \(S\)에 속한 \(S\)를 dominating set이라고 부릅니다. 크기가 큰 dominating set을 구하는 것은 쉬우니 크기가 가장 작은 dominating set을 찾는 것이 흥미로운 문제겠죠.

Dominating set problem

---

어떤 그래프 \(G = ( V, E )\)와 자연수 \(k\)가 주어졌을 때, 크기가 \(k\)를 넘지 않는 dominating set이 존재하는지 판별하시오.

 

이 문제는 \(k\)-center problem의 inapproximability와 metric \(k\)-center problem의 \(\mathsf{NP}\)-hardness를 보이는 데 사용되었죠. 이를 증명할 때 사용된 가장 중요한 아이디어는 dominating set problem의 solution이 그대로 \(k\)-center problem의 solution으로 해석될 수 있다는 점이었습니다. 즉, dominating set problem의 입력을 요리조리 수정하여 우리가 원하는 \(k\)-center problem의 입력을 만들고 이를 해결하면 그대로 dominating set problem을 해결할 수 있었습니다.

 

이번에는 반대로 가 보려고 합니다. 지난 번에는 dominating set problem에서 \(k\)-center problem으로 갔다면, 이번에는 \(k\)-center problem에서 dominating set problem으로 가는 것이죠. 매우 비슷해 보이고, 실제로도 비슷하지만, 이 둘의 방향은 엄연히 다릅니다. 자, \(k\)-center problem의 입력은 지점 집합 \(V\)와 거리 \(d\)이고 여기서 구하고자 하는 것은 가장 작은 \(\tau_S\)를 구하는 것입니다. 반면 dominating set problem의 입력은 그래프 \(G\)이고 이 문제를 해결하면 얻을 수 있는 것은 만약 존재한다면 크기가 \(k\)를 넘지 않는 dominating set입니다. 과연 dominating set problem을 "이용"해서 어떻게 \(k\)-center problem을 해결할 수 있을까요?

그림 1. \(k\)-center problem 입력 예시

아이디어는 다음과 같습니다. 우리가 \(k\)-center problem의 입력에다 어떤 역치값 \( \tau \)를 추측해 보겠습니다. 만약 두 지점 사이의 거리가 \(\tau\)를 넘으면 아예 고려를 하지 않으려고 합니다. 좀 더 엄밀히 말씀을 드리자면, \(k\)-center problem의 입력 \( V, d \)에 대해서 \(E_{\leq \tau}\)를 거리가 \(\tau\)를 넘지 않는 지점의 쌍을 연결한 것, 즉,

\[ E_{\leq \tau} := \{ (u, v) : d(u, v) \leq \tau \}\]

으로 정의하겠습니다. 추가로 \(G_{\leq \tau} := (V, E_{\leq \tau}) \)로 정의하겠습니다.

 

만약 \(G_{\leq \tau}\)에 크기가 \(k\)보다 작거나 같은 dominating set \(S \subseteq V\)가 존재한다면 어떻게 될까요? 이 문제에서 선택된 \(S\)를 그대로 \(k\)-center problem에 가지고 오겠습니다. 그러면 우리는 모든 지점 \(v\)에 대해서 \(S\) 중 적어도 한 지점까지는 \(\tau\)보다 멀지 않다는 것을 알 수 있습니다. 다시 말해, \[ d(S, v) \leq \tau \]라는 의미죠. 그 이유는 dominating set의 정의를 유심히 살펴보면 쉽게 알 수 있습니다. 이를 통해서 우리는 주어진 \(k\)-center problem의 입력의 optimal value \(\tau^\star\)가 \(\tau\)를 넘지 않는다는 것을 알 수 있게 됩니다.

그림 2. \(k = 3\)보다 크지 않은 dominating set이 존재하는 \(G_{\leq \tau}\) 예시

반대로, \(G_{\leq \tau}\)에 크기가 \(k\)보다 작거나 같은 dominating set이 존재하지 않는다면 어떨까요? 그러면 원래 문제인 \(k\)-center problem의 주어진 입력에 대해서 최대 \(k\)개만 뽑아서 모든 지점을 거리 \(\tau\) 이내로 선택한 지점에 할당하는 방법이 존재하지 않는다는 의미입니다. 그렇지 않다면 \(G_{\leq \tau}\)에 solution이 존재하지 않았을리가 없겠죠. 다시 말해, \(\tau^\star > \tau\)를 의미하는 것이죠.

그림 3. \(k = 3\)보다 크지 않은 dominating set이 존재하지 않는 \(G_{\leq \tau}\)의 예시

자, 여기서 문제는 우리가 처음에 역치값 \(\tau\)를 추측했다는 것이죠. 이 \(\tau\)의 범위는 도대체 어떻게 될까요? 일단, 0보다는 크거나 같을 것입니다. 또, \( \max_{u, v \in V} d(u, v) \)보다는 작거나 같을 것입니다. 하지만 이 범위 안에는 무수히 많은 숫자가 존재하죠. 이들 모두를 고려한다는 것은 불가능합니다. 어떻게 해야할까요?

 

다행히도 우리가 고려할 숫자는 그다지 많지 않습니다. 잘 생각해 보면, \(\tau^\star\)는 \( d(u, v) \) 중 하나로 결정이 될 것입니다. 우리가 하는 것이 지점 몇 곳을 선정해서 다른 지점들을 선택된 지점에 할당하는 것인데 \(d(u, v)\) 중 하나로 결정이 되지 않을 수가 없겠죠? 따라서 서로 다른 \(d(u, v)\)에 대해서만 고려해 주면 됩니다. 거리 \(d(u, v)\)는 최대 \(O(|V|^2)\) 개의 서로 다른 숫자를 가질 수 있습니다. 따라서 우리는 \(O(|V|^2)\)번만 위 작업을 해주면 \(k\)-center problem을 해결할 수 있을 것입니다.^[ㄱ]

Metric 활용하기

앞에서 한 가지 얼렁뚱땅 넘어간 것이 있습니다. 도대체 어떻게 dominating set을 구한다는 것이죠? 안타깝게도 dominating set problem은 \(\mathsf{NP}\)-complete 합니다. 현재로서는 효율적으로 해결하는 방법이 존재하지 않는다는 뜻이죠. 그러니 앞에서 우리가 아무리 \(\tau\)를 잘 추측해 보았자 \(G_{\leq \tau}\)에 대해서 dominating set을 구하지 못하므로 말짱 도루묵이 되었습니다.

 

우리는 이를 "근사적"으로 해결하고자 합니다. 들어가기에 앞서서 나중에 요긴하게 쓰일 것들을 정의하고 넘어가겠습니다. 어떤 그래프 \(G = (V, E)\)가 주어졌을 때, 두 정점 \(u, v \in V\)에 대해서 \(u\)에서 \(v\)까지 도달하는 데 필요한 간선의 최솟값을 \(\mathsf{dist}_G (u, v)\)로 나타내겠습니다. 만약 그래프가 문맥 상 모호하지 않으면 아래첨자 \(G\)를 지우고 \(\mathsf{dist}(u,v) \)로도 표현할 수 있습니다.

 

위 정의에 따라 다시 쓰면 dominating set은 임의의 정점 \(v \in V\)에 대해서

\[\mathsf{dist} (u, v) \leq 1\]

인 \(u\)가 \(S\)에 존재하는 정점 집합 \(S \subseteq V\)입니다. 여기서 거리가 1보다 작거나 같다는 조건은 너무 빡빡하니, 다음과 같이 늘려주면 어떨까요? 즉, 임의의 정점 \(v \in V\)에 대해서

\[ \mathsf{dist} (u, v) \leq 2 \tag{1}\]

인 \(u\)가 \(S\)에 존재하는 \(S\)를 구하는 것이죠.

 

이러한 \(S\)를 구하는 것이 왜 도움이 될까요? 바로 우리가 고려하는 그래프가 \(G_{\leq \tau}\)이기 때문입니다. 이 그래프에서 간선 \((u, v)\)는 원래 문제인 \(k\)-center problem에서 \(d(u,v) \leq \tau\)를 나타낸 것이었습니다. 그렇다면, \( \mathsf{dist}_{G_{\leq \tau}} (u, v) = 2 \)는 원래 문제에서 어떻게 될까요? 네, 바로 \(d(u, v) \leq 2 \tau\)를 의미합니다. 왜냐고요? 바로 metric의 triangle inequality 때문입니다.^[ㄴ]

 

게다가 식 (1)을 만족하면서 \( |S| \leq k \)인 \(S\)가 \(G_{\leq \tau}\)에 존재하는 \( \tau \) 중 가장 작은 값을 \( \tau_\mathsf{min}\)이라고 하면 우리는

\[ \tau_\mathsf{min} \leq \tau^\star \tag{2} \]

도 이끌어낼 수 있습니다. 왜냐하면 \(G_{\leq \tau^\star}\)에는 이미 크기가 \(k\)보다 작거나 같은 dominating set이 존재하며 이는 자연스럽게 식 (1)도 만족을 시키기 때문입니다.

 

앞에서 고려한 내용들을 통해 다음과 같은 정리를 이끌어낼 수 있습니다.

정리 1. Reduction

---

Metric \(k\)-center problem의 입력을 \(V, d, k\)라고 하자. 만약 임의의 추측값 \(\tau\)에 대해서

1. \(G_{\leq \tau} \)에서 \(|S| \leq k\)이고 임의의 정점 \(v \in V\)에 대해 \( \mathsf{dist}_{G_{\leq \tau}} (u, v) \leq 2\)를 만족하는 \(u\)가 \(S\)에 존재하는 정점 집합 \(S \subseteq V\)를 반환하거나;
2. \(G_{\leq \tau} \)에는 크기가 \(k\)보다 작거나 같은 dominating set이 존재하지 않는다는 것을 알려주는

알고리즘이 존재한다면, 우리는 metric \(k\)-center problem에 대한 2-근사 알고리즘을 만들 수 있다.

대부분 앞에서 설명이 되었기 때문에 딱히 증명이라고 할 것도 없어 보입니다. 그래도 한 번 더 정리를 해 보죠. 정리 1에서 가정한 알고리즘을 \(\mathcal{A}\)라고 하겠습니다. 우리가 보이고자 하는 것은 metric \(k\)-center problem을 근사비 2로 해결하는 알고리즘을 만드는 것입니다. 방법은 간단합니다. 먼저 역치 \(\tau\)를 추측합니다. 위에서 우리가 고려할 \(\tau\)는 서로 다른 \(d(u,v)\)로 \(O(|V|^2)\)개만 따져보면 됩니다.

 

그 후, \(G_{\leq \tau}\)를 입력으로 \(\mathcal{A}\)를 수행합니다. 알고리즘의 수행이 성공하여 1번 조건을 만족하는 \(S\)를 반환한다면, 우리는 그대로 \(S\)가 원래 문제에서 \(\tau_S \leq 2\tau\)가 되는 것을 알 수 있습니다. 그 중 가장 작은 값인 \(\tau_\mathsf{min}\)은 식 (2)에 의해서 \(\tau^\star\)보다 작거나 같기 때문에 \(\tau_\mathsf{min}\)에의 \(S\)는

\[ \tau_S \leq 2 \tau_\mathsf{min} \leq 2 \tau^\star\]

를 만족하며, 이것으로 2-근사 알고리즘을 얻을 수 있습니다.

Strong stable set

따라서 이제 우리의 목표는 정리 1에서 가정한 알고리즘이 실지로 존재한다는 것을 보이는 것입니다. 시작하기에 앞서 몇 가지를 정의하고 넘어가도록 하죠. 먼저 어떤 정점 \(u \in V\)와 자연수 \(k\)가 주어졌을 때, \(u\)에서 거리가 \(k\)보다 크지 않은 정점들의 집합을 \(N^k (u)\)라고 하겠습니다. 즉,

\[ N^k(u) := \{ v \in V : \mathsf{dist}_G(u,v) \leq k \}\]

입니다. 만약 \(k\)가 1인 경우 위첨자 없이 \(N(u)\)로 쓸 수도 있습니다.

 

다음으로 어떤 그래프 \(G = (V, E)\)가 주어졌을 때, 임의의 정점 \(v \in V\)에 대해서 \(v\)와 \(v\)에 인접한 정점 중 최대 한 개만 \(S\)에 포함되는 정점 집합 \(S \subseteq V\)를 strong stable set이라고 정의하겠습니다. 앞에서 정의한 기호를 사용하여 표현하면, 모든 \(v \in V\)에 대해서

\[ |N(v) \cap S| \leq 1 \]

을 만족하는 \(S \subseteq V\)가 되겠습니다.

그림 4. Strong stable set 예시

이를 정의한 이유는 바로 strong stable set이 항상 dominating set보다 크기가 작기 때문입니다.

정리 2. Strong stable set & dominating set

---

임의의 그래프 \(G = (V, E)\)에 대해서, \(S_\mathsf{stable} \subseteq V\)은 \(G\) 위의 어떤 strong stable set이라고 하고 \(S_\mathsf{dom} \subseteq V\)는 \(G\) 위의 한 dominating set이라고 하자. 그러면

\[ |S_\mathsf{stable}| \leq |S_\mathsf{dom}|\]

이 항상 성립한다.

증명을 해보죠. 귀류법을 써 보겠습니다. 다시 말해, \(|S_\mathsf{stable}| > |S_\mathsf{dom}|\)이라고 가정해 보겠습니다. 이제부터 \(S_\mathsf{dom}\)에서 정점 \(u\)를 하나 선택하고 \(u\)와 함께 \(u\)에 인접하지만 \(S_\mathsf{dom}\)에는 속하지 않은 정점들을 지우려고 합니다. 즉, \(u\)가 선택되었을 때, 우리가 이번에 지울 정점 집합 \(T_u\)는

\[ T_u := \{ u \} \cup \left( N(u) \setminus S_\mathsf{dom} \right) \]

으로 나타낼 수 있습니다. 이 작업이 모두 끝나면 그래프의 모든 정점이 지워지게 될 것입니다. 왜냐면 dominating set의 정의 상 그래프의 모든 정점은 \(S_\mathsf{dom}\)에 속하거나 그것에 속한 정점에 인접해야 하기 때문입니다.

 

여기서 strong stable set과 연관된 흥미로운 점이 생깁니다. 바로 모든 \(T_u\)에 대해서

\[ |T_u \cap S_\mathsf{stable}| \leq 1 \]

이라는 점입니다. 만약 그렇지 않다면 \(N(u)\)에 두 개 이상의 \(S_\mathsf{stable}\)에 속한 정점이 존재한다는 의미이고, 이는 strong stable set의 조건에 위배되기 때문입니다.

 

따라서 \(T_u\)를 지울 때마다 최대 한 개의 \(S_\mathsf{stable}\)의 정점이 지워지게 됩니다. 문제는 처음에 \( |S_\mathsf{stable}| > |S_\mathsf{dom}| \)이라고 가정했다는 점이죠. 그러니 \(T_u\)를 모조리 지워도 분명 지워지지 않을 \(S_\mathsf{stable}\)의 정점이 하나 존재하게 됩니다. 하지만 이는 \(S_\mathsf{dom}\)이 dominating set이라는 사실에 위배됩니다. 따라서 모순이 발생하므로 우리의 정리가 성립하게 되죠.

 

정리 2를 통해서 우리는 다음을 쉽게 추론해 낼 수 있습니다.

정리 3. 정리 2의 corollary

---

만약 어떤 그래프 \(G = (V, E)\)에서 크기가 \(k\)보다 큰 strong stable set을 찾으면, \(G\)에는 크기가 \(k\)보다 작거나 같은 dominating set이 존재하지 않는다.

이는 정리 1의 2번 조건을 위한 토대가 됩니다.

그림 5. 그림 3의 그래프가 3보다 작거나 같은 dominating set을 갖지 못하는 이유

알고리즘 및 분석

지금까지 알아낸 것을 기반으로 정리 1에서 가정한 알고리즘을 만들어 보겠습니다. 위 정리에서는 \(G_{\leq \tau}\)로 입력을 특정하였지만, 아래에서는 일반적인 입력에 대해서 기술하도록 하겠습니다.

정리 1에서 가정한 알고리즘

---

입력 : 그래프 \(G = (V, E) \), 자연수 \(k\)

출력 : \( |S| \leq k \)이며 임의의 정점 \( v \in V\)에 대해 \( \mathsf{dist}_G (u, v) \leq 2\)인 \(u \in S\)가 존재하는 \(S \subseteq V\)

예외 : 크기가 \( k \)를 넘지 않는 dominating set이 \(G\)에 존재하지 않음

 

1. \( S \gets \emptyset \), \( T \gets V \)
2. \(|T| > 0\)일 동안 아래를 반복 :
   
   1. \(T\)의 한 정점 \(u\)를 선정
   2. \(S \gets S \cup \{ u \} \)
   3. \(T \gets T \setminus N^2(u) \)
3. 만약 \( |S| > k \) 이면, 예외 발생
4. \(S\) 반환

간단히 알고리즘을 설명하면, 남아있는 정점 하나를 선택하고 그 정점에서 최대 두 개의 간선으로 갈 수 있는 모든 정점을 다 지우는 것입니다. 그리고 이 작업을 최대한 하는 것이죠. 최대 두 개의 간선으로 갈 수 있는 모든 정점, 즉 \(N^2(u)\)를 지우는 이유는 쉽게 확인할 수 있습니다. \(u\)가 \(S\)의 일원이 되었으니 \(N^2(u)\)의 정점 \(v\)는 \(\mathsf{dist}(u, v) \leq 2\)이기 때문입니다.

 

그렇다면 \(|S| > k\)일 때, 예외를 발생시킬 수 있는 이유는 무엇일까요? 바로 이렇게 만든 \(S\)가 strong stable set이기 때문입니다.

정리 4. Correctness

---

이 알고리즘이 출력하는 \(S\)는 다음을 만족한다.

1. 임의의 정점 \(v \in V\)에 대해 \(\mathsf{dist} (u, v) \leq 2\)인 \(u \in S\)가 존재한다.
2. \(S\)는 \(G\)의 strong stable set이다.

정리 4의 1번 조건은 앞에서 보였으니 넘어가겠습니다. 문제는 2번 조건인데, 이는 귀납적으로 보이겠습니다. 처음 \(S\)는 공집합이므로 자명하게 strong stable set입니다. 이제 알고리즘의 2번 반복문을 수행하는 어떤 순간에 \(S\)가 strong stable set이라고 가정하겠습니다. \(|T| = 0\)이면 그대로 반환되므로 고민할 필요가 없죠. 반대의 경우에는 \(u \in T\)를 \(S\)에 추가하게 됩니다. 만약 \(S \cup \{ u \}\)가 여전히 strong stable set이라면 증명은 모두 끝나게 됩니다.

 

여기서는 귀류법을 적용해 보죠. 만약 \(S \cup \{ u \} \)가 strong stable set이 아니라면 이미 \(S\)에 들어온 정점 \(w \in S\) (\( w \neq u \))와 strong stable set의 조건을 위배하도록 만드는, \(u\)와 \(w\)에 동시에 인접한 어떤 정점 \(v \in V\)가 있을 것입니다. 그 말인 즉슨, \( \mathsf{dist}_G (u, w) \leq 2 \)라는 뜻이며 이는 \( u \in N^2(w) \)를 의미하죠. 즉, \(w\)가 \(S\)에 선택되었을 때 \(u\)는 원래 삭제되었어야 하므로 모순이 발생하게 됩니다.

 

이것으로 정리 4를 증명하였습니다. 따라서 \(|S| > k\)라면 정리 3에 의해서 예외를 발생시킬 수 있고, 반대로 \(|S| \leq k\)라면 모든 정점에서 최대 두 개의 간선을 사용하여 \(S\)의 정점에 도달할 수 있는, 즉 원래 문제인 metric \(k\)-center problem에서는 추측값 \(\tau\)에 대해 모든 지점에서 최대 \(2 \tau\) 내로 선정된 지점에 도달하는 방법을 찾을 수 있게 됩니다.

마치며

이것으로 metric \(k\)-center problem을 해결하는 2-근사 알고리즘에 대해서 알아보았습니다. 시작할 때는 이렇게 글이 길어지리라고 생각하지는 못했는데, 막상 쓰면 쓸 수록 글이 계속 길어지는 것을 느꼈습니다. 그래도 알고리즘의 중요한 포인트들은 최대한 짚었다고 생각합니다.

 

이 알고리즘에서 가장 핵심적인 부분은 역치값을 추측하는 것입니다. 이 방법은 \(k\)-center problem과 같이 최댓값을 최소화하는, 이른바 병목 문제(bottleneck problem)을 해결하는 데 가장 널리 사용되는 기법입니다. 어차피 최댓값을 최소화하는 것이므로 임의로 역치를 두어 이 값 이상으로는 고려 자체를 하지 않는다면 아무리 못해도 역치에 해당하는 값을 넘지 못할 것입니다. 만약 우리가 따져봐야하는 역치의 개수가 그렇게 많지 않고, 역치가 정해졌을 때에는 문제를 어렵지 않게 해결할 수 있다면 좋은 (근사) 알고리즘을 얻을 수 있을 것입니다.

 

서두에도 말했지만 학기가 시작하니 글을 쓰기가 쉽지 않군요. 그래도 마음 나는 대로 꾸준히 써 보도록 하겠습니다. 읽어주셔서 고맙습니다.

참조

[1] D. S. Hochbaum and D. B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of operations research, 1985.

주석

[ㄱ] 이는 binary search를 사용하면 \(O( \log |V| )\)으로 줄일 수 있습니다.

 

[ㄴ] Metric의 정의는 다음과 같습니다. 지점 집합 \(V\)가 주어졌을 때, 임의의 지점 \(u, v, w \in V\)에 대해서 (1) \(d(u, u) = 0 \), (2) \( d(u, v) = d(v, u)\), (3) \( d(u, v) \leq d(u, w) + d(w, v)\)를 만족하는 \(d\)를 metric이라고 합니다.