지난 포스트에서 우리는 설비 후보지들이 주어질 때 최소의 비용으로 몇 곳의 후보지에 설비를 지어 모든 고객을 서비스하는 방법을 찾는 설비 입지 선정 문제(facility location problem)를 공부하였습니다. 언뜻 보기에도 산업적으로 유용해 보이는 이 문제는 이론적으로도 흥미로운 부분이 많아서 널리 연구가 되었습니다. 지난 포스트에서는 그중에서도 특히 이 문제를 해결하는 4-근사 알고리즘을 배웠습니다.
설비 입지 선정 문제 (Facility Location Problem)
여러분이 큰 물류 회사를 경영한다고 가정해 봅시다. 여러분에게는 수많은 고객들이 있으며 여러분은 그들에게 상품을 배송해 주어야 합니다. 이를 위해서는 몇몇 장소에 큰 물류 창고를 건설
gazelle-and-cs.tistory.com
해당 알고리즘은 다음과 같이 동작하였습니다. 먼저, 주어진 입력을 적절힌 표현하는 선형 계획법 완화(linear programming relaxation, LP relaxation)를 구하였습니다. 그러고 난 후, 이 LP와 그것의 쌍대(dual) LP를 풀어서 얻은 LP 최적해들을 적당히 반올림(round)하여 최종 해를 구하였습니다.
이 알고리즘에서 한 가지 아쉬운 점을 꼽자면 바로 LP를 풀어야 한다는 것입니다. LP는 원래 문제를 잘 반영해 줄 뿐더러 타원체 기법(ellipsoid method) 등의 적절한 알고리즘을 통해 다항 시간에 해결할 수 있어서 수많은 근사 알고리즘의 모체로서 역할을 하였습니다. 하지만 LP를 직접 푸는 것은 실제로는 오차도 많이 발생하고 그다지 효율적이지도 않은 일입니다. 따라서 만약 LP를 직접 풀지 않고도 LP의 성질을 활용하여 좋은 근사해를 얻을 수 있다면, 이론적으로도 실질적으로도 좋은 성능을 보일 것을 기대할 수 있습니다.
이번 포스트에서는 설비 입지 선정 문제를 해결하는 3-근사 알고리즘을 제시합니다. 특히 LP를 직접 풀지 않으면서도 LP의 다양한 성질들을 활용하여 알고리즘을 분석합니다.
복습
들어가기에 앞서 지난 시간에 배운 내용을 가볍게 복습해 보겠습니다. 먼저 문제의 입력은 아래와 같이 주어집니다.
- 설비의 집합 \(F\)와 고객의 집합 \(D\)
- 각 설비 \(i \in F\)에 대해, 개설 비용 \(o_i\)
- 각 설비 \(i \in F\)와 각 고객 \(j \in D\)에 대해, 삼각 부등식을 만족하는 할당 비용 \(c_{ij}\)
우리의 목표는 몇몇 설비를 실제로 개설한 후 모든 고객을 개설된 설비 한 곳에 할당하면서 비용을 최소화시키는 것입니다. 다시 말해, 개설할 설비를 \(S \subseteq F\), 각 고객의 할당을 \(\sigma : V \to S\)라고 했을 때, \( \sum_{j \in D} c_{\sigma(j) j} + \sum_{i \in S} o_i \)를 최소화하는 것이 목표입니다.
또한 아래의 LP는 이 문제의 적절한 LP 완화임을 공부했습니다.
\[ \begin{array}{rll} \text{minimize } & \displaystyle \sum_{j \in D} \sum_{i \in F} c_{ij} x_{ij} + \sum_{i \in F} o_i y_i & \\ \text{subject to } & y_i \geq x_{ij}, & \forall i \in F, \forall j \in D, \\ & \displaystyle \sum_{i \in F} x_{ij} = 1, & \forall j \in D, \\ & x_{ij}, y_i \geq 0, & \forall i \in F, \forall j \in D. \end{array} \tag{P} \]
아래는 위의 원 문제(primal program)의 쌍대 문제입니다.
\[ \begin{array}{rll} \text{maximize } & \displaystyle \sum_{j \in D} v_j & \\ \text{subject to } & v_j \leq c_{ij} + u_{ij}, & \forall i \in F, \forall j \in D, \\ & \displaystyle \sum_{j \in D} u_{ij} \leq o_i, & \forall i \in F, \\ & u_{ij} \geq 0, & \forall i \in F, \forall j \in D. \end{array} \tag{D} \]
위 쌍대 문제를 직관적으로 이해하는 방법도 소개하였습니다만, 이는 이번 포스트에서 아주 요긴한 개념이므로 다음 절에서 다시 제대로 서술하도록 하겠습니다. 마지막으로 LP의 약한 쌍대성(weak duality)에 의해 아래의 정리가 성립함을 알 수 있습니다.
정리 1. 약한 쌍대성(weak duality)
쌍대 문제 (D)에 가능한 어떤 해 \((u, v)\)에 대해, \( \sum_{j \in D} v_j \)는 원 문제 (P)의 최적값보다 작거나 같다.
쌍대 문제의 직관적 해석
상술한 대로 쌍대 문제 (D)를 직관적으로 해석하는 방법이 존재합니다. 이번에는 모든 고객이 서비스를 받기 위해 출자를 한다고 해 보겠습니다. 각 고객 \(j \in D\)는 \(v_j\)만큼의 금액을 준비했다고 하겠습니다. 이 고객이 어떤 설비 \(i \in F\)에 투자하기 위해서는 먼저 둘 사이의 할당 비용인 \(c_{ij}\)를 내야 합니다. 그러고도 투자금이 남아 있으면(즉, \(v_j \geq c_{ij}\)라면), \(v_j - c_{ij}\)만큼을 설비 \(i \in F\)를 개설하기 위해 투자할 수 있습니다. 이 추가분을 \( u_{ij} := \max \{ v_j - c_{ij}, 0 \} \)이라고 하겠습니다. 그러면 자연스럽게 각 고객 \(j \in D\)는 각각의 설비 \(i \in F\)에 대해, \[ v_j \leq c_{ij} + u_{ij} \tag{1} \]를 만족한다는 것을 알 수 있습니다. 이는 (D)의 첫 번째 제약 조건에 해당합니다.
설비 \(i \in F\)를 개설하기 위해서는 \(o_i\)의 금액이 필요하며, 이 비용은 고객들의 투자금으로부터 충당하고자 합니다. 하지만 고객들은 충분히 똑똑하기 때문에 과투자할 생각이 없습니다. 다시 말해, \[ \sum_{j \in D} u_{ij} \leq o_i \tag{2} \]를 만족한다는 말입니다. 그렇지 않다면 이 설비에 투자할 여력이 있는 어떤 고객이 자신의 투자금을 약간 줄여도 여전히 해당 설비를 개설할 수 있는 충분한 금액을 얻을 수 있을 테고, 해당 고객이 이를 마다할 리 없습니다. 이는 (D)의 두 번째 제약 조건에 해당합니다.
각 고객의 출자금 \(\{v_j\}_{j \in D}\)이 위 조건을 모두 만족한다고 하겠습니다. 그러면 총 출자금 \(\sum_{j \in D} v_j\)는 어떤 설비를 개설하고 각 고객을 개설된 설비에 어떻게 할당하든지 간에 그것의 총비용보다 크지 않습니다. 예를 들어, 우리가 \(S \subseteq F\)를 개설하고, 각 고객 \(j\)를 \(\sigma(j) \in S\)에 할당하였다고 해 보겠습니다. 어떤 개설된 설비 \(i \in S\)에 할당된 고객들을 \(\sigma^{-1}(i)\)라고 할 때, 이 고객들이 해당 설비 \(i\)의 개설에 투자하는 총금액은 \[ \sum_{j \in \sigma^{-1}(i)} u_{ij} \leq \sum_{j \in D} u_{ij} \leq o_i \]를 만족합니다. 그러므로, \[ \begin{array}{rl} \displaystyle \sum_{j \in D} c_{\sigma(j) j} + \sum_{i \in S} o_i & \displaystyle \geq \sum_{j \in D} c_{\sigma(j) j} + \sum_{i \in S} \sum_{j \in \sigma^{-1}(i)} u_{ij} \\ & \displaystyle = \sum_{j \in D} (c_{\sigma(j) j} + u_{\sigma(j) j}) \\ & \displaystyle \geq \sum_{j \in D} v_j \end{array} \]가 성립합니다. 여기서 마지막 부등식은 조건 (1)를 통해 유도할 수 있습니다.
알고리즘 설계
위 해석을 바탕으로 이제 다음 방법을 생각해 봅시다. 처음에는 모든 고객이 0의 투자금을 갖고 있습니다. 이후 각 고객들은 동일한 속도로 자신의 투자금을 늘려 갑니다. 어떤 설비 \(i\)에 대해 투자금 \(v_j\)가 \(c_{ij}\)를 넘어서면, 그때부터 고객 \(j\)는 설비 \(i\)의 개설에 \(u_{ij} := v_j - c_{ij}\)만큼 투자할 수 있습니다. 그러다 만약 어떤 설비 \(i\)에 개설하기 충분한 투자금이 모이면, 다시 말해, \( \sum_{j \in D} u_{ij} = o_i \)가 되면, 해당 설비 \(i\)를 개설하고, 이 설비의 개설에 기여를 한 고객들을 모두 해당 설비에 할당합니다. 이렇게 할당된 고객들은 서비스를 받고 있으므로 더 이상 투자금을 늘릴 이유가 없으므로 더 이상 투자금을 늘리지 않고 멈춥니다. 이 과정을 모든 고객들이 서비스를 받게 될 때까지 지속합니다.
예시와 함께 위 방법을 자세히 설명해 보겠습니다. 우리에게 다음과 같은 입력이 주어졌다고 해 보겠습니다.
이제 모든 고객이 동일한 속도로, 예컨대, 1초에 1원씩 자신의 투자금을 증가시킨다고 해 보겠습니다. 그러면 1초 때에는 아래와 같은 상황이 될 것입니다.
현재까지는 고객들의 투자금이 적으므로 할당 비용조차 낼 수 없습니다. 하지만 3초 때에는 고객 A의 투자금이 위쪽 설비로의 할당 비용을 모두 충당하게 됩니다.
따라서 이 이후로 고객 A는 위쪽 설비의 개설에 기여할 수 있습니다. 4초 때에는 1원을 투자할 수 있을 것입니다.
동시에 고객 B는 두 설비 모두로의 할당 비용을 감당할 수 있을만큼의 투자금을 유치했음을 확인하시기 바랍니다. 따라서 이 이후로 B는 두 설비 각각의 개설에 기여할 수 있습니다.
5초 때에는 다음과 같이 위쪽 설비에 충분한 투자금이 모이게 된다는 것을 알 수 있습니다.
따라서 위쪽 설비를 개설하도록 하죠.
이 설비의 개설에 기여할 수 있는 고객은 A와 B입니다. 따라서 해당 고객들을 위쪽 설비에 할당해 주도록 하겠습니다. 두 고객은 서비스를 받게 되었으므로, 이 시각 이후로는 투자금을 늘릴 이유가 없습니다. 따라서 남은 C와 D만 투자금을 늘려 줍니다.
6초 때에는 아래와 같이 고객 D가 아래쪽 설비의 개설에 1만큼 기여합니다.
따라서 이번에는 아래쪽 설비도 개설하여 주도록 하겠습니다.
아래쪽 설비의 개설에 기여를 할 수 있는 고객은 B와 D입니다. 이 중에서 고객 D는 아직 서비스를 받지 못한 상태였으므로 투자금이 남아있는 상태입니다. 하지만 고객 B는 사정이 다릅니다. 이미 위쪽 설비를 개설하면서 본인의 투자금을 전부 소진한 상태죠. 따라서 아래쪽 설비를 개설할 때 필요한 비용에서 B가 내어줄 수 있다고 했던 1의 투자금만큼 비게 됩니다. 이 부분이 바로 이 문제를 해결하는 것이 어려워지는 지점입니다. 다만, 이를 해결하는 것은 나중으로 미루고 일단은 아래쪽 설비를 개설했다고 하고 알고리즘을 진행해 보겠습니다.
현재까지의 투자금으로 아직 할당될 설비를 찾지 못한 고객은 C뿐입니다. 7초 때에 고객 C의 투자금은 다음과 같이 아래쪽 설비로의 할당 비용을 충당할 수 있을만큼 모이게 됩니다.
아래쪽 설비는 개설된 상태이므로, 고객 C를 아래쪽 설비에 할당하는 것은 매우 자연스러운 선택입니다. 이제 모든 고객이 개설된 설비에 할당이 되었으므로 전체 과정을 종료합니다.
그 결과는 다음과 같습니다. 설비는 위쪽 아래쪽 모두 개설하기로 하였습니다. 고객 A와 B는 위쪽 설비에 할당하였고, 나머지 고객 C와 D는 아래쪽 설비에 할당하였습니다. 이를 도식화하면 아래와 같습니다.
하지만 앞에서 언급한 대로, 이 결과에는 큰 문제점이 하나 있습니다. 바로 현재 고객들이 출자한 총액으로 모든 비용을 충당할 수 없다는 점입니다. 이런 현상이 발생한 이유는 바로 고객 B 때문이죠. 두 설비 모두에게 양의 기여를 할 수 있다고 해 놓고는 위쪽 설비가 개설되자마자 대뜸 거기에 투자를 하고 잠적을 탔기 때문입니다. 따라서 나중에 개설이 결정된 아래쪽 설비의 개설 비용을 충당할 수 없게 되고 말았습니다.
이를 어떻게 해결할 수 있을까요? 고객 B는 고객 A와 함께 위쪽 설비에 실제로 투자를 했습니다.즉, 위쪽 설비의 개설 비용과 고객 A와 B의 할당 비용은 두 고객의 투자금으로 충분히 감당할 수 있습니다. 대신 아래쪽 설비의 개설 비용은 충분하지 못한 상태이므로, 이 설비를 닫아야 하겠습니다. 자연히 아래쪽 설비에 할당되어 있던 고객 C와 D는 어쩔 수 없이 위쪽 설비에 할당이 되어야 하겠는데요. 여기서 우리는 각 고객의 할당 비용이 해당 고객이 준비한 투자금의 세 배를 넘지 않음을 보일 수 있습니다.
고객 D를 예시로 설명을 해 보겠습니다. 할당 비용은 삼각 부등식을 만족하므로 고객 D가 위쪽 설비에 할당되는 비용은 다음의 세 비용의 합보다 크지 않습니다.
- 고객 D가 아래쪽 설비에 할당되는 비용
- 고객 B가 아래쪽 설비에 할당되는 비용
- 고객 B가 위쪽 설비에 할당되는 비용
이때, 고객 D가 아래쪽 설비의 개설에 기여를 하였다는 뜻은 D의 투자금이 할당 비용을 넘어섰다는 의미입니다. 같은 이치로 고객 B는 두 설비의 개설에 모두 기여를 했으므로 각각으로의 할당 비용은 B의 투자금을 넘지 못합니다. 따라서 첫 번째 비용은 D의 투자금으로, 아래 두 비용은 B의 투자금으로 상한을 줄 수 있습니다. D보다 B가 먼저 투자금 증대를 멈추었으므로 D의 투자금이 B의 투자금보다 많습니다. 이를 종합하면 고객 D를 위쪽 설비에 할당하는 비용은 D의 투자금의 세 배를 넘지 않습니다.
위와 같은 방식으로 고객 C를 위쪽 설비에 할당하는 비용이 C의 투자금의 세 배를 넘지 않음을 알 수 있습니다. 따라서 아래와 같이 모든 고객을 위쪽 설비에 할당하여 주는 방법의 총비용은 고객들이 준비한 투자금의 세 배를 넘지 않는다는 것을 이끌어 낼 수 있습니다.
위 논의를 바탕으로 다음의 알고리즘을 고안해 봅시다. 아래 알고리즘이 기술된 바를 살펴보면, LP를 풀지 않는다는 것을 확인할 수 있습니다. 대신 직접 \(v\)와 \(u\)를 구성하고 있으며, 이렇게 얻은 \((u, v)\)는 쌍대 문제 (D)에 가능한 해가 됩니다. 이후 LP의 약한 쌍대성을 통해 아래의 알고리즘이 근사 알고리즘이 된다는 것을 보일 것입니다. 이처럼 LP를 푸는 대신 직접 원/쌍대 문제에 가능한 해―경우에 따라서는 근사적으로 가능한 해―를 구하고 분석에서 LP의 성질을 활용하는 알고리즘을 일컬어 원-쌍대 알고리즘(primal-dual algorithm)이라고 부릅니다.
알고리즘 1. 설비 입지 선정 원-쌍대 3-근사 알고리즘
입력: 설비 \(F\), 고객 \(D\), 개설 비용 \(o\), 할당 비용 \(c\)
출력: 개설된 설비 \(S \subseteq F\), 할당 \( \sigma : D \to S \)
- 각 고객 \(j\)의 투자금 \(v_j\)를 0으로 설정한다.
- \(D_\mathsf{rem} \gets D\), \( S_\mathsf{temp} \gets \emptyset \).
- \(D_\mathsf{rem}\)이 공집합이 될 때까지 아래를 반복한다.
- 아래의 두 상황 중 하나가 발생할 때까지 아직 할당되지 못한 각 고객 \(j \in D_\mathsf{rem}\)의 투자금 \(v_j\)를 같은 속도로 동시에 증가시킨다. 단, 각 \(j \in D\), \(i \in F\)에 대해, \( u_{ij} := \max \{ v_j - c_{ij}, 0 \} \)으로 정의하고, 동시에 발생한 상황들은 아무 순서로 하나씩 진행한다.
- 아직 개설되지 않은 설비 \(i \in F \setminus S_\mathsf{temp}\)에 충분한 기여가 모인 경우. 즉, \(\sum_{j \in D} u_{ij} = o_i\)를 만족하는 \(i\)가 발생한 경우.
- \(S_\mathsf{temp} \gets S_\mathsf{temp} \cup \{i\} \)
- \(D_i \gets \{j \in D \mid u_{ij} > 0 \} \)
- \(D_\mathsf{rem} \gets D_\mathsf{rem} \setminus D_i \)
- 할당되지 못한 고객 \(j \in D_\mathsf{rem}\)와 이미 개설된 설비 \(i \in S_\mathsf{temp}\)에 대해, \(j\)의 투자금이 \(i\)로의 할당 비용을 충당할 수 있게 된 경우. 즉, \( v_j = c_{ij} \)가 된 경우.
- \(D_\mathsf{rem} \gets D_\mathsf{rem} \setminus \{j\} \)
- 아직 개설되지 않은 설비 \(i \in F \setminus S_\mathsf{temp}\)에 충분한 기여가 모인 경우. 즉, \(\sum_{j \in D} u_{ij} = o_i\)를 만족하는 \(i\)가 발생한 경우.
- 아래의 두 상황 중 하나가 발생할 때까지 아직 할당되지 못한 각 고객 \(j \in D_\mathsf{rem}\)의 투자금 \(v_j\)를 같은 속도로 동시에 증가시킨다. 단, 각 \(j \in D\), \(i \in F\)에 대해, \( u_{ij} := \max \{ v_j - c_{ij}, 0 \} \)으로 정의하고, 동시에 발생한 상황들은 아무 순서로 하나씩 진행한다.
- \(S \gets \emptyset\).
- \(S_\mathsf{temp}\)의 각 설비 \(i\)를 \(S_\mathsf{temp}\)에 들어간 순서대로 순회하며 아래를 수행한다.
- 만약 \(i\)와 어떤 \(i' \in S\)의 개설에 동시에 양의 기여를 하는 고객이 존재하면, 다시 말해, \( D_i \cap D_{i'} \neq \emptyset \)인 \(i' \in S\)이 존재하면, 아무것도 하지 않고 다음 설비를 고려한다.
- 그러한 \(i' \in S\)가 존재하지 않으면, \(i\)를 \(S\)에 넣고 다음 설비를 고려한다.
- 각 \(i \in S\)에 대해, 투자금이 설비 \(i\)로의 할당 비용을 충당할 수 있을 때 모든 고객을 여기에 할당한다. 즉, \(c_{ij} \leq v_j\)인 \(j\)에 대해, \(\sigma(j) \gets i\).
- 앞의 단계에서 할당되지 못한 각 고객 \(j\)은 반드시 \(v_j \geq c_{ij}\), \(v_j \geq v_{j'}\), \(u_{ij'}, u_{i'j'} > 0\)을 만족하는 설비 \(i \in S_\mathsf{temp} \setminus S\)와 \(i' \in S\), 고객 \(j' \in D\)가 존재하며, \(\sigma(j) \gets i'\).
이 알고리즘의 수행 시간을 생각해 보겠습니다. 알고리즘은 연속된 시간에 걸쳐서 투자금을 증가시키고 있어서, 그 자체로는 너무 많은 시간이 필요해 보입니다. 하지만 두 상황 3-A-i과 3-A-ii 중 하나가 발생할 때까지는 투자금을 증가시키기만 하므로, 어떤 상황이 발생할 때까지 필요한 투자금 증가량을 매번 계산한다면 이 알고리즘을 이산적으로 변환할 수 있습니다. 해당 증가량을 구하는 것은 다항 시간에 수행할 수 있으며, 상황이 발생할 때마다 \(D_\mathsf{rem}\)에서 고객이 적어도 하나씩은 제거되므로 단계 3을 반복한 횟수도 많지 않습니다. 나머지 단계들은 다항 시간에 동작하는 것을 쉽게 확인할 수 있습니다.
근사비 분석
이제 이 알고리즘이 3-근사 알고리즘이라는 것을 증명해 보겠습니다. 앞에서 그림과 함께 설명한 예시에서의 논의를 잘 확장한다면, 이 알고리즘이 유지하는 투자금 \(\{v_j\}_{j \in D}\)와 각 설비로의 기여 \(\{u_{ij} := \max(v_j - c_{ij}, 0)\}_{i \in F, j \in D}\)가 쌍대 문제 (D)에 가능한 해라는 것을 알 수 있습니다. 그러므로 정리 1에 의해 총 투자금 \(\sum_{j \in D} v_j\)는 적절한 최적값의 하한을 이룹니다. 따라서 \[ \sum_{j \in D} c_{\sigma(j) j} + \sum_{i \in S} o_i \leq 3 \sum_{j \in D} v_j \]임을 보이면 이 알고리즘이 3-근사 알고리즘이라는 것을 증명할 수 있습니다. 아래에서는 다음과 같이 이것보다 강한 명제를 증명해 보고자 합니다.
정리 2. 알고리즘의 근사비
알고리즘의 출력 \(S, \sigma\)에 대해, \[ \sum_{j \in D} c_{\sigma(j) j} + 3 \sum_{i \in S} o_i \leq 3 \sum_{j \in D} v_j \]를 만족한다.
강해진 부분은 개설 비용의 계수입니다. 즉, 이 알고리즘이 출력하는 답안의 개설 비용을 본래보다 세 배 지불해도 총 투자금의 세 배를 넘지 않는다는 뜻입니다. 이러한 성질을 만족하는 알고리즘을 라그랑주 승수 보존 알고리즘(Lagrangian multiplier preserving algorithm, LMP algorithm)이라고 일컫습니다.
단계 6에서 할당이 된 고객들의 집합을 \(D_\mathsf{dir}\), 단계 7에서 할당된 고객들의 집합을 \(D_\mathsf{ind}\)라고 부르겠습니다. 또한 각 설비 \(i \in F\)에 대해, \(D_i := \{j \in D \mid u_{ij} > 0\}\)를 \(i\)의 개설에 양의 기여를 한 고객의 집합으로 정의했음을 상기하시기 바랍니다.
먼저, 개설된 설비 \(i \in S\)에 대해 \(D_i\)는 서로 겹치지 않음을 보이겠습니다.
정리 3. 서로소인 \(\{D_i\}_{i \in S}\)
임의의 서로 다른 \(i, i' \in S\)에 대해, \(D_i \cap D_{i'} = \emptyset\)이다.
[증명] 어떤 두 \(i, i' \in S\)에 대해 \(D_i \cap D_{i'} \neq \emptyset\)이라고 해 보겠습니다. 일반성을 잃지 않고 \(i'\)이 단계 5에서 먼저 고려되어 \(S\)에 들어갔다고 하겠습니다. 그러면 단계 5에서 \(i\)를 고려할 적에 단계 5-A의 조건에 위배되어 \(i\)는 \(S\)에 들어가지 않았을 것입니다. ■
이제 \(D_\mathsf{dir}\) 고객들의 총 할당 비용을 계산해 보겠습니다.
정리 4. \(D_\mathsf{dir}\)의 총 할당 비용
\(\displaystyle \sum_{j \in D_\mathsf{dir}} c_{\sigma(j) j} = \sum_{j \in D_\mathsf{dir}} v_j - \sum_{i \in S} o_i\).
[증명] 임의의 \( i \in F, j \in D \)에 대해 \(u_{ij} = \max\{v_j - c_{ij}, 0\}\)으로 정의되었습니다. 단계 6의 동작에서 우리는 임의의 \(j \in D_\mathsf{dir}\)에 대해, \( u_{\sigma(j) j} = v_j - c_{\sigma(j) j} \)가 됨을 알 수 있습니다. 그러므로 \[ \sum_{j \in D_\mathsf{dir}} c_{\sigma(j) j} = \sum_{j \in D_\mathsf{dir}} v_j - \sum_{j \in D_\mathsf{dir}} u_{\sigma(j) j} = \sum_{j \in D_\mathsf{dir}} v_j - \sum_{i \in S} \sum_{j \in \sigma^{-1}(i) \cap D_\mathsf{dir}} u_{ij} \]를 이끌어 낼 수 있습니다.
위 식의 마지막 변의 두 번째 항이 \(\sum_{i \in S} o_i\)와 동일함을 보이면 증명이 끝납니다. 설비 \(i \in S\)가 개설되는 데에 양의 기여를 하는 고객들 \(D_i\)는 단계 6에 의해 바로 할당이 됩니다. 따라서 \[ \sum_{i \in S} \sum_{j \in \sigma^{-1}(i) \cap D_\mathsf{dir}} u_{ij} = \sum_{i \in S} \sum_{j \in D_i} u_{ij} = \sum_{i \in S} o_i \]가 성립합니다. 여기서 첫 번째 등식은 정리 3에 의해 \(\{D_i\}_{i \in S}\)가 서로소여서 성립하고, 마지막 등식은 단계 3-A-i의 조건에 의해 만족됩니다. ■
이번에는 \(D_\mathsf{ind}\)에 집중해 봅시다. 먼저 단계 7이 올바르다는 것을 보이겠습니다.
정리 5. 단계 7의 올바름
임의의 \(j \in D_\mathsf{ind}\)에 대해, 다음을 만족하는 설비 \(i, i'\)과 고객 \(j'\)이 존재한다.
- \(i \in S_\mathsf{temp} \setminus S\), \(i' \in S\).
- \(v_j \geq c_{ij}\).
- \(j' \in D_i \cap D_{i'}\).
[증명] 알고리즘이 종료하였다는 뜻은 상황 3-A-i든지 3-A-ii에 의해 \(j\)가 어떤 \(i \in S_\mathsf{temp}\)에 대해 \(v_j \geq c_{ij}\)를 만족했다는 것입니다. 하지만 \(j\)가 단계 6에서 할당되지 못했다는 의미는 해당 \(i\)보다 먼저 \(S_\mathsf{temp}\)에 들어가면서 \( D_i \cap D_{i'} \neq \emptyset \)를 만족하는 \(i' \in S\)가 존재한다는 것입니다. ■
그러면 단계 6에서 할당되지 못한 고객의 최종 할당 비용의 상한을 다음과 같이 구할 수 있습니다.
정리 6. \(D_\mathsf{ind}\) 고객의 할당 비용 상한
각 고객 \(j \in D_\mathsf{ind}\)에 대해, \(c_{\sigma(j) j} \leq 3 v_j\)를 만족한다.
[증명] 정리 5에서 보장된 설비 \(i, i'\)과 고객 \(j'\)을 가지고 오겠습니다. \(\sigma(j) = i'\)으로 설정됩니다. 그러면, \[ c_{i'j} \leq c_{ij} + c_{ij'} + c_{i'j'} \leq v_j + 2 v_{j'} \leq 3 v_j \]를 유도할 수 있습니다. 이때 첫 번째 부등식은 할당 비용의 삼각 부등식에서, 두 번째 부등식은 정리 5의 조건에서 각각 이끌어 낼 수 있습니다. 마지막 부등식은 \(i'\)이 \(i\)보다 \(S_\mathsf{temp}\)에 먼저 들어가고, 그때 \(j'\)은 투자금 \(v_{j'}\)의 증가를 멈추지만 \(v_j\)는 계속 증가할 수 있으므로 성립합니다. ■
이제 주 정리인 정리 2를 증명할 수 있습니다.
[정리 2 증명] 정리 4와 정리 6을 통해 \[ \sum_{j \in D} c_{\sigma(j) j} \leq 3 \sum_{j \in D_\mathsf{dir}} c_{\sigma(j) j} + \sum_{j \in D_\mathsf{ind}} c_{\sigma(j) j} \leq 3 \sum_{j \in D} v_j - 3 \sum_{i \in S} o_i\]를 얻을 수 있습니다. ■
마치며
이것으로 설비 입지 선정 문제를 LP를 풀지 않고 분석에서만 활용하여 근사해를 출력하는 원-쌍대 3-근사 알고리즘에 대한 소개를 마칩니다. 추가적으로 우리는 본문의 알고리즘이 총 개설 비용에 대해서는 세 배를 더 지불하여도 근사비를 유지할 수 있는 라그랑주 승수 보존성을 갖는다는 것도 공부하였습니다. 라그랑주 승수 보존성은 매우 중요한 성질로서 특히 \(k\)-중앙값 문제(\(k\)-median problem)를 해결하는 데 요긴하게 활용됩니다. 다음에는 이 기법을 포스팅해 보겠습니다.
사실 다른 문제를 해결할 때 라그랑주 승수 보존성을 활용할 수 있을지 연구하던 차에 본문의 알고리즘을 깊이 공부했어서 이 참에 이번 글을 작성하였습니다. 글을 마무리하는 현재에는 원래 풀고자 하는 문제에 대한 긍정적인 결과와 부정적인 결과를 모두 얻은 상태입니다. 더 좋은 결과가 되기를 바라 봅니다.
읽어 주셔서 고맙습니다. :)
참고 자료
[1] David P. Williamson and David B. Shmoys. The design of approximation algorithms. Cambridge university press, 2011.
'근사 알고리즘 > Facility location' 카테고리의 다른 글
| 설비 입지 선정 문제 (Facility Location Problem) (6) | 2022.10.03 |
|---|---|
| [k-Center Problem] 2-근사 알고리즘 (0) | 2019.09.24 |
| [k-Center Problem] 문제 정의 (0) | 2019.08.16 |
