여러분이 큰 물류 회사를 경영한다고 가정해 봅시다. 여러분에게는 수많은 고객들이 있으며 여러분은 그들에게 상품을 배송해 주어야 합니다. 이를 위해서는 몇몇 장소에 큰 물류 창고를 건설해야 하겠죠. 여러 곳에서 자문을 얻어 물류 창고를 건설할 후보지를 받아 놓았다고 합시다. 이제 여러분은 큰 결단의 기로에 서게 됩니다. 바로 후보지 중 어느 곳에 물류 창고를 건설할지 결정해야 합니다. 고려해야 하는 요인은 크게 두 가지입니다. 하나는 각 후보지마다 물류 창고를 건설하게 될 때 발생할 비용일 것이고, 다른 하나는 물류 창고에서 각 고객에게 상품을 배송할 때 들어가는 비용입니다. 경영자의 입장에서 여러분은 당연히 총 비용이 최소가 되도록 하고 싶습니다. 과연 어느 후보지에 물류 창고를 건설하면 될까요?
실제 회사에서 쉽게 일어날 법한 위 예시와 같은 상황을 정형화한 문제가 바로 설비 입지 선정 문제(facility location problem)입니다. 이 문제는 이론적으로도 흥미로울 뿐더러 산업적으로 유용하여 깊이, 그리고 널리 연구가 되었는데요. 이번 포스트에서는 이 문제가 어떤 것인지 알아 보고, 이 문제를 해결하는 4-근사 알고리즘을 제시하도록 하겠습니다.
문제 정의
이번 절에서는 문제를 정확히 정의해 보겠습니다. 문제의 입력은 다음과 같이 이루어집니다. 먼저 설비(facility)의 집합 \(F\)가 주어집니다. 사실, 설비의 후보지라고 부르는 것이 좀더 정확하겠지만, 편의를 위해 그냥 설비라고 부르겠습니다. 각 설비 \(i \in F\)에 대해, 만약 이 설비를 설치한다면 개설 비용(opening cost)으로 \(o_i\)의 비용이 발생한다고 하겠습니다. 동시에 고객(client)의 집합 \(D\)도 주어집니다. 그리고 어떤 고객 \(j \in D\)를 설비 \(i \in F\)에 할당한다면 \(c_{i,j}\)의 할당 비용(assignment cost)이 발생합니다. 우리는 \(F\) 중 몇몇 설비를 실제로 개설하고, 모든 고객을 개설된 설비 중 한 곳에 할당해야 합니다. 이 상황에서 우리의 목표는 당연히 발생한 총 비용을 최소화하는 것이 됩니다.
만약 할당 비용 \(c\)에 아무런 조건이 없다면 상수의 근사비로는 해결하기 힘들 것이라는 사실이 잘 알려져 있습니다.[ㄱ] 따라서 본문에서 우리는 \(c\)에 다음과 같은 강력하지만 합리적인 조건을 부여하고자 합니다.
- 임의의 두 설비 \(i, i' \in F\)와 임의의 두 고객 \(j, j' \in D\)에 대해, \(c_{i, j} \leq c_{i, j'} + c_{i', j'} + c_{i', j}\)를 만족한다.
위 조건을 다시 말하자면 고객 \(j\)를 설비 \(i\)에 곧장 할당하는 비용이 다른 고객 \(j'\)과 다른 설비 \(i'\)을 "경유"하여 할당하는 것보다 좋다는 것입니다. 만약 \(c\)가 일종의 거리라면 위 부등식이 자연스럽게 다가올 것입니다. 이러한 부등식을 우리는 (비록 총 네 개의 지점이 참여하고 있지만) 삼각 부등식(triangle inequality)이라고도 부릅니다.
안타깝지만, 이 조건이 있는 경우에도 설비 입지 선정 문제는 NP-난해(NP-hard)하다는 사실이 잘 알려져 있습니다.[ㄴ] 대신, 이번에는 상수의 근사비를 갖는 근사 알고리즘을 고안할 수 있습니다. 그 방법에 대해서 차차 알아 보도록 하겠습니다.
선형 계획법으로 표현하기
많은 조합론적 최적화 문제를 해결하는 방법 중 하나는 해당 문제를 정수 계획법(integer programming)으로 나타내는 것입니다. 설비 입지 선정 문제도 다음과 같은 정수 계획 문제(integer program)로 표현할 수 있습니다.
\[ \begin{array}{lrll} \text{minimize} & \displaystyle \sum_{j \in D} \sum_{i \in F} c_{i, j} x_{i, j} & \displaystyle + \; \sum_{i \in F} o_i y_i \\ \text{subject to} & y_i & \geq x_{i, j}, & \forall i \in F, \forall j \in D, \\ & \displaystyle \sum_{i \in F} x_{i, j} & = 1, & \forall j \in D, \\ & x_{i, j}, y_i & \in \{0, 1\}, & \forall i \in F, \forall j \in D. \end{array} \]
위 문제를 해석해 보겠습니다. 먼저 변수(variable)에 대한 설명입니다. 변수 \(x_{i, j}\)는 고객 \(j\)가 설비 \(i\)에 할당이 되었을 때 1의 값을 갖습니다. 변수 \(y_i\)는 설비 \(i\)가 개설되었을 때 1의 값을 갖습니다.
이제 제약 조건(constraint)이 실제 문제의 가능한 해(feasible solution)를 잘 표현하고 있다는 것을 보이겠습니다. 첫 번째 제약 조건은 고객이 개설된 설비에 할당되어야 함을 나타냅니다. 고객 \(j\)가 어떤 설비 \(i\)에 할당이 된 상황은 \(x_{i, j} = 1\)로 표현합니다. 이때, 이 제약 조건에 의해 \(y_i = 1\)이어야 하고, 이는 설비 \(i\)가 개설되어야 한다는 의미입니다. 두 번째 제약 조건은 고객이 정확히 하나의 설비에 할당되어야 함을 나타냅니다. 어떤 고객 \(j\)에 대해, 모든 \(x_{i, j}\)가 0 또는 1의 값을 가질 수 있을 때, 그것들의 합이 1이라면 정확히 하나의 \(x_{i, j}\)만 1의 값을 가지게 될 것입니다.
위 제약 조건들을 모두 만족한다면 목적 함수(objective function) 또한 우리가 최적화하고자 하는 총 비용을 나타낸다는 것을 쉽게 확인할 수 있습니다. 첫 번째 항은 총 할당 비용을, 두 번째 항은 총 개설 비용을 나타냅니다.
따라서 이 정수 계획 문제는 설비 입지 선정 문제를 잘 표현하고 있습니다. 하지만 일반적으로 정수 계획법은 NP-난해하여 빠른 시간에 해결하는 것을 기대하기 어렵습니다. 이러한 현상이 발생하는 가장 큰 이유는 바로 세 번째 제약 조건인 정수 제약 조건(integrality constraint) 때문인데요. 이 조건을 다음과 같이 완화한 선형 계획 문제(linear program)를 생각해 봅시다.
\[ \begin{array}{lrll} \text{minimize} & \displaystyle \sum_{j \in D} \sum_{i \in F} c_{i, j} x_{i, j} & \displaystyle + \; \sum_{i \in F} o_i y_i \\ \text{subject to} & y_i & \geq x_{i, j}, & \forall i \in F, \forall j \in D, \\ & \displaystyle \sum_{i \in F} x_{i, j} & = 1, & \forall j \in D, \\ & x_{i, j}, y_i & \geq 0, & \forall i \in F, \forall j \in D. \end{array} \]
정수 계획법과 달리 선형 계획법(linear programming)은 다항 시간에 해결할 수 있음이 잘 알려져 있습니다.[ㄷ] 그러므로 우리는 이 문제의 최적해(optimal solution)를 안다고 가정해도 괜찮습니다. 비록 정수 제약 조건이 누락되어 그 최적해는 0과 1이 아닌 그 사이의 분수로 이루어질 수 있지만, 그럼에도 다른 제약 조건들을 모두 만족하므로 우리에게 도움이 될 것을 예상할 수 있습니다. 특히, 아래 정리는 정수 조건이 완화되었기에 쉽게 얻을 수 있는 사실입니다.
정리 1. 완화된 문제의 최적해의 성질
정수 조건이 완화된 선형 계획 문제의 최적해를 \((x^*, y^*)\)라고 하고, 실제 설비 입지 선정 문제의 최적값을 \(\mathsf{OPT}\)라고 하자. 그러면, \[ \sum_{j \in D} \sum_{i \in F} c_{i, j} x^*_{i, j} + \sum_{i \in F}o_i y^*_i \leq \mathsf{OPT}\]를 만족한다.
참고로, 이렇게 정수 계획법의 정수 제약 조건을 완화하는 기법 및 그 결과를 우리는 선형 계획법 완화(linear programming relaxation) 혹은 LP-완화(LP-relaxation)라고 부릅니다.
선형 계획법의 흥미로운 특질 중 하나는 바로 쌍대성(duality)입니다. 쌍대 문제(dual program)는 원 문제(primal program)의 최적의 하한(lower bound)을 표현합니다. 이와 관련하여는 제가 예전에 다룬 적이 있으므로 궁금하신 분들은 아래 글을 참고하시면 되겠습니다.
[선형 계획법] 쌍대성(Duality)
Linear programming은 최적화 분야에서 잘 알려지고 연구되었으며 실제로도 많이 응용되는 기법입니다. 줄여서 LP라고도 하며, 우리말로는 선형계획법으로 불립니다. 이름이 뭔가 멋들어져서 괜스레
gazelle-and-cs.tistory.com
아래에 소개할 근사 알고리즘은 위 선형 계획 문제의 쌍대 문제도 필요합니다. 이는 다음과 같습니다. (변환 과정은 생략합니다. 위 글을 참고하셔서 직접 해 보시는 것도 추천합니다.)
\[ \begin{array}{lrll} \text{maximize} & \displaystyle \sum_{j \in D} v_j & & \\ \text{subject to} & v_j - u_{i, j} & \leq c_{i, j}, & \forall i \in F, \forall j \in D, \\ & \displaystyle \sum_{j \in D} u_{i,j} & \leq o_i, & \forall i \in F, \\ & u_{i, j} & \geq 0, & \forall i \in F, \forall j \in D. \end{array} \]
여기서 변수 \(u_{i, j}\)는 원 문제의 첫 번째 제약 조건인 \(y_i \geq x_{i, j}\)에 대응합니다. 변수 \(v_j\)는 두 번쨰 제약 조건인 \(\sum_{i \in F} x_{i, j} = 1\)에 대응합니다. 참고로 이 제약 조건은 등식이므로 \(v_j\)는 양수든 음수든 아무 값을 가질 수 있습니다.
위 쌍대 문제를 보다 직관적으로 해석하는 방법을 소개하겠습니다. 이를 위해서는 설비 입지 선정 문제를 고객이 직접 출자하여 설비를 개설하는 문제로 생각하면 좋습니다. 각 고객 \(j \in D\)가 \(v_j\)의 금액을 투자한다고 합시다. 이 고객이 설비 \(i\)를 개설하기 위해서는 일단 \(c_{i, j}\)의 금액을 내야 합니다. 하지만 각 설비는 개설 비용이 추가로 들어 갑니다. 이를 위해 각 고객 \(j \in D\)가 설비 \(i\)에 \(w_{i, j}\)만큼 투자한다고 하겠습니다. 그러면 고객 \(j\)는 분명 \( c_{i, j} + w_{i, j} \)가 가장 적게 드는 금액만큼 출자하려고 할 것입니다. 즉, 임의의 설비 \(i \in F\)에 대해, \[v_j \leq c_{i, j} + w_{i, j}\]를 만족해야 합니다. 이는 위 쌍대 문제의 첫 번째 제약 조건에 해당하죠.
이제 어떤 설비 \(i \in F\)의 입장에서 보겠습니다. 이를 개설하기 위해서 총 \( \sum_{j \in D} w_{i, j} \)의 투자금이 모였습니다. 다만 고객들의 입장에서 필요한 금액인 \(o_i\)보다 많은 금액을 투자할 이유는 없으므로, \[ \sum_{j \in D} w_{i, j} \leq o_i \]가 만족한다고 볼 수 있습니다. 이는 쌍대 문제의 두 번째 제약 조건에 해당하는 것을 알 수 있습니다.
이 두 제약 조건을 통해서 우리는 쌍대 문제가 원 문제의 적절한 하한을 이룬다는 것을 알 수 있습니다. 각 고객 \(j\)는 결국 어느 설비 \(i\)에는 할당이 되어야 하며, 그러면 \( c_{i, j} + w_{i, j} \)만큼 투자를 해야하고, 첫 번째 제약 조건을 통해 \(v_j\)가 이 값의 적절한 하한이 됨을 알 수 있습니다. 게다가 설비 \(i\)가 개설되면 \(o_i\)의 비용이 발생하며, 두 번째 제약 조건에 의해 \(w_{i, j}\)의 합이 이를 넘지 않아 하한의 성질을 만족한다는 것을 확인할 수 있습니다. 다시 말해 아래의 정리가 성립합니다.
정리 2. 약한 쌍대성 (Weak duality)
원 문제에 가능한 해 \((x, y)\)와 쌍대 문제에 가능한 해 \((u, v)\)가 주어졌다고 하자. 그러면 항상 \[ \sum_{j \in D} \sum_{i \in F} c_{i, j} x_{i, j} + \sum_{i \in F} o_i y_i \geq \sum_{j \in D} v_j \]가 성립한다.
쌍대 문제도 선형 계획 문제입니다. 그러므로 이 문제도 원 문제와 같이 다항 시간에 효율적으로 해결할 수 있습니다. 아래에서 소개할 근사 알고리즘은 원 문제의 최적해와 쌍대 문제의 최적해가 모두 필요합니다. 두 최적해 사이에는 다음과 같은 흥미로운 성질이 성립합니다. 이는 알고리즘을 분석할 때 매우 요긴하게 사용됩니다.
정리 3. 두 최적해 사이의 성질
원 문제의 한 최적해 \((x^*, y^*)\)와 쌍대 문제의 한 최적해 \((u^*, v^*)\)가 주어졌다고 하자. 만약 어떤 설비 \(i\)와 고객 \(j\)에 대해 \(x^*_{i, j} > 0\)이라면 \(v^*_j = c_{i, j} + u^*_{i, j} \geq c_{i, j}\)를 항상 만족한다.
위 정리는 선형 계획법의 complementary slackness와 \(u^*_{i, j} \geq 0\)이라는 조건을 활용하여 쉽게 증명할 수 있습니다. Complementary slackness가 궁금하신 분은 위에서 공유한 제 이전 글을 읽어 보시기 바랍니다. (도무지 complementary slackness의 마뜩한 번역이 떠오르지를 않습니다. 어떻게 번역하면 좋을까요?)
근사 알고리즘 및 분석
지금까지 설비 입지 선정 문제를 선형 계획법으로 표현하는 방법에 대해서 알아 보았습니다. 특히 원 선형 계획 문제의 최적해 \((x^*, y^*)\)와 그것의 쌍대 문제의 최적해 \((u^*, v^*)\)를 다항 시간에 구할 수 있다고 했는데요. 이제 이를 활용하여 알고리즘을 만들어 보겠습니다. 먼저 한 가지 정의할 것이 있는데요. 임의의 고객 \(j \in D\)에 대해, \(N(j)\)는 \(x^*\)에서 \(j\)와 0보다 큰 값으로 연결된 설비의 집합, \(N^2(j)\)는 \(x^*\)에서 \(N(j)\)의 한 설비에서 0보다 큰 값으로 연결된 모든 고객의 집합이라고 정의하겠습니다. 다시 말해, \[N(j) := \{i \in F \mid x^*_{i, j} > 0\}, \; N^2(j) := \{j' \in D \mid \exists i \in N(j), x^*_{i, j'} > 0\}\]를 의미합니다.
이제 알고리즘을 소개하겠습니다.
알고리즘 1. 4-근사 알고리즘
입력: 설비 집합 \(F\), 고객 집합 \(D\), 개설 비용 \(o\), 할당 비용 \(c\)
출력: 몇 개의 설비를 개설하고 모든 고객을 개설된 설비에 할당하는 방법
- 원 선형 계획 문제의 최적해 \((x^*, y^*)\)와 쌍대 문제의 최적해 \((u^*, v^*)\)를 구한다.
- 할당되지 않은 고객이 없을 때까지 아래를 반복한다.
- 할당되지 않은 고객 중 \(v^*_j\)의 값이 가장 작은 고객을 \(j^\circ\)라고 하자.
- \(N(j^\circ)\)에서 가장 개설 비용이 적은 설비를 \(i^\circ\)라고 하고, 이 설비를 개설한다.
- \(N^2(j^\circ)\) 중 아직 어딘가에 할당되지 않은 모든 고객을 \(i^\circ\)에 할당하고, 이들을 고려 대상에서 제외한다.
이 알고리즘이 올바른 출력을 반환한다는 것은 쉽게 알 수 있습니다. 할당되지 않은 고객이 없을 때까지 단계 2를 계속 반복하기 때문입니다. 만약 어떤 고객 \(j\)가 계속 할당되지 않은 채로 남아 있었다면, 이는 필경 모든 설비 \(i \in F\)에 대해 \(x^*_{i, j} = 0\)이라는 뜻입니다. 원 문제에 \(\sum_{i \in F} x_{i, j} = 1\)이라는 제약 조건이 있으므로, 그런 상황은 발생할 수 없습니다.
또한 이 알고리즘이 다항 시간에 동작하는 것도 어렵지 않게 확인할 수 있습니다. 단계 1은 이전 절에서 논의하였으며, 단계 2는 최대 \(O(|D|)\) 번 수행됩니다. 단계 2의 세부 단계들도 모두 어렵지 않게 다항 시간에 동작하도록 구현할 수 있습니다.
따라서 이제 남은 것은 이 알고리즘이 근사해를 출력한다는 사실을 증명하는 것입니다. 알고리즘이 출력하는 해의 총 개설 비용과 총 할당 비용을 나누어서 분석해 보겠습니다.
먼저 총 개설 비용이 그리 크지 않음을 보이겠습니다. 단계 2-a에서 선정된 고객들의 집합을 \(\mathcal{C}\)라고 부르겠습니다. 그러면 다음의 흥미로운 성질을 어렵지 않게 확인할 수 있습니다.
정리 4. \(N(j^\circ)\)의 서로소 관계
\(\mathcal{C}\)의 서로 다른 두 고객 \(j_1^\circ, j_2^\circ\)에 대해, \(N(j_1^\circ) \cap N(j_2^\circ) = \emptyset\)을 만족한다.
[증명] 일반성을 잃지 않고 \( j_1^\circ \)가 먼저 뽑혔다고 하겠습니다. 만약 \( N(j_1^\circ) \cap N(j_2^\circ) \neq \emptyset \)이라면, 분명 \(j_2^\circ \in N^2(j_1^\circ)\)가 됩니다. 그러면 단계 2-c에 의해 \(j_2^\circ\)는 단계 2-a에서 선택될 수 없습니다. ■
이제 총 개설 비용의 상한을 구할 수 있습니다.
정리 5. 총 개설 비용의 상한
알고리즘이 출력하는 해의 총 개설 비용 \( \sum_{j^\circ \in \mathcal{C}} o_{i^\circ} \)은 \( \sum_{i \in F} o_i y^*_i \)를 넘지 않는다.
[증명] 정리 4에 의해 \(j^\circ \in \mathcal{C}\)의 \( N(j^\circ) \)는 서로소 관계를 이루므로, \[ \sum_{i \in F} o_i y^*_i \geq \sum_{j^\circ \in \mathcal{C}} \sum_{i \in N(j^\circ)} o_i y^*_i \]가 만족합니다. 그러면 원 문제의 제약 조건에 의해, \[ \sum_{j^\circ \in \mathcal{C}} \sum_{i \in N(j^\circ)} o_i y^*_i \geq \sum_{j^\circ \in \mathcal{C}} \sum_{i \in N(j^\circ)} o_i x^*_{i, j^\circ} \geq \sum_{j^\circ \in \mathcal{C}} o_{i^\circ} \]이 성립합니다. 여기서 첫 번째 부등식은 첫 번째 제약 조건에 의해서 곧장 유도할 수 있으며, 두 번째 부등식은 두 번째 제약 조건인 \( \sum_{i \in F} x_{i, j^\circ} = 1 \)이라는 점과 \(i^\circ\)가 \(N(j^\circ)\) 중에서 가장 개설 비용이 작다는 사실을 통해 얻을 수 있습니다. ■
위 정리와 정리 1을 통해 우리는 알고리즘이 지불하는 총 개설 비용이 실제 최적값 \(\mathsf{OPT}\)를 넘지 않음을 보일 수 있습니다.
이번에는 총 할당 비용도 그리 많이 내지 않는다는 사실을 보이겠습니다. 그동안 쌍대 문제에 대한 최적해를 사용하지 않아서 의아하셨을 텐데, 여기서 활용이 됩니다.
정리 6. 각 고객의 할당 비용의 상한
각 고객 \(j \in D\)의 할당 비용은 \(3v^*_j\)를 넘지 않는다.
[증명] 만약 \(N(j)\) 중 한 설비가 개설되어 \(j\)가 그 설비에 할당이 되었다고 하겠습니다. 그러면 정리 3에 의해 그 할당 비용이 \(v^*_j\)를 넘지 않음을 쉽게 알 수 있습니다. 따라서 \(j\)가 \(N(j)\)에 속하지 않은 설비에 할당이 된 경우만 고려하면 됩니다. 알고리즘의 동작을 고려해 보면, 이 상황은 분명 어떤 \(j^\circ \in \mathcal{C}\)에 대해
- \(j \in N^2(j^\circ) \)
- \(i^\circ \not\in N(j) \)
를 만족하는 경우에 발생할 것입니다. \(j\)를 \(N^2(j^\circ) \)에 속하게 만드는 설비를 \(i \in N(j^\circ) \cap N(j)\)라고 하겠습니다. 그러면 삼각 부등식에 의해 \(j\)를 \(i^\circ\)에 할당하는 비용은 \[ c_{i^\circ, j} \leq c_{i^\circ, j^\circ} + c_{i, j^\circ} + c_{i, j} \]를 만족합니다. 우변의 마지막 항은 \(i \in N(j)\)이므로 정리 3에 의해 \(v^*_j\)를 넘지 않습니다. 반면, 첫 두 항은 \(i, i^\circ \in N(j^\circ)\)이므로 정리 3에 의해 모두 \(v^*_{j^\circ}\)를 넘지 않음을 알 수 있습니다. 알고리즘의 단계 2-a에 의해 \(v^*_{j^\circ} \leq v^*_j\)가 만족합니다. 이를 모두 결합하면 정리의 명제를 증명할 수 있습니다. ■
그러므로 알고리즘이 내는 총 할당 비용은 정리 6에 의해 \( 3 \sum_{j \in D} v^*_j \)를 넘지 않습니다. 정리 2와 정리 1을 차례로 적용하면 이 비용이 최적값의 세 배를 넘지 않는다는 것을 얻을 수 있습니다. 앞에서 얻은 총 개설 비용에 대한 상한을 더하면 알고리즘 1이 4-근사 알고리즘임을 확인할 수 있습니다.
마치며
이것으로 설비 입지 선정 문제에 대한 설명을 마칩니다. 이번 포스트에서 공부한 4-근사 알고리즘은 이 문제를 선형 계획법 완화로 표현하여 최적해를 구한 후 이를 활용하여 실제 문제의 해를 구하는 방법입니다. 이러한 기법을 우리는 선형 계획법 반올림(linear programming rounding) 혹은 LP-반올림(LP-rounding) 기법이라고도 부릅니다. 이 기법은 설비 입지 선정 문제에서뿐 아니라 수많은 조합론적 최적화 문제의 근사 알고리즘을 구하는데 활용되었습니다.
삼 년 전 \(k\)-중심 문제(\(k\)-center problem)에 대해서 정리하였습니다. 이 문제도 설비 입지 선정 문제와 매우 유사합니다. 가장 큰 차이점은 \(k\)-중심 문제는 최대 거리를 최소화하는 병목 최적화(bottleneck optimization) 문제인데 반해 설비 입지 선정 문제는 비용의 총합을 최소화하는 최소합 최적화(min-sum optimization) 문제라는 것입니다. \(k\)-중심 문제를 정리한 후에 빨리 설비 입지 선정 문제도 정리하고 싶었는데, 삼 년이 지난 지금에서야 정리를 완료하였네요.
서두에서도 밝혔듯이 설비 입지 선정 문제는 산업적으로 유용하면서도 이론적인 분석이 가능하여 학계에서 매우 깊이 그리고 널리 연구가 되었습니다. 이번 글에서 보여드린 선형 계획법 반올림 기법뿐 아니라 국소 탐색 알고리즘(local search algorithm) 및 원-쌍대 알고리즘(primal-dual algorithm) 등 이 문제를 해결하는 다양한 근사 알고리즘이 존재합니다. 또한 이 글의 알고리즘을 발전시키면 현재보다 훨씬 좋은 근사비의 알고리즘도 얻을 수 있습니다. 뿐만 아니라 다양한 변종(variant)으로도 널리 연구가 되었는데요. 몇 가지만 소개를 드리면, 용량이 있는 설비 입지 선정 문제(capacitated facility location problem), \(k\)-중간값 문제(\(k\)-median problem) 등이 있습니다. 위 내용들도 흥미로운 것들이 많으니 기회가 되면 정리해 보도록 하겠습니다.
읽어 주셔서 고맙습니다.
참고 문헌
[1] David P. Williamson and David B. Shmoys. The design of approximation algorithms. Cambridge university press, 2011.
각주
[ㄱ] 아무 조건이 없는 설비 입지 선정 문제의 특수한 경우 중 하나는 집합 덮개 문제(set cover problem)입니다. 집합 덮개 문제는 합리적인 가정 하에 \(\Omega(\log n)\)의 근사비가 최선이라는 사실이 알려져 있습니다.
[ㄴ] 삼각 부등식 조건을 만족하는 설비 입지 선정 문제를 다항 시간에 정확히 해결할 수 있으면 집합 덮개 문제를 정확히 해결할 수 있습니다. 집합 덮개 문제는 [ㄱ]에서도 알 수 있다시피 유명한 NP-난해한 문제 중 하나입니다.
[ㄷ] 타원면법(ellipsoid method)으로 변수의 개수와 제약 조건의 개수의 다항 시간에 선형 계획법을 해결할 수 있다는 사실이 잘 알려져 있습니다. 하지만 실질적으로는 단체법(simplex method)이 훨씬 빠른 수행 시간을 보인다고 합니다. 그렇지만 아직 단체법을 다항 시간에 수행하는 방법은 모르는 것으로 알고 있습니다.
'근사 알고리즘 > Facility location' 카테고리의 다른 글
| 설비 입지 선정 원-쌍대 근사 알고리즘 (Primal-Dual Approximation Algorithm for Facility Location) (0) | 2024.01.27 |
|---|---|
| [k-Center Problem] 2-근사 알고리즘 (0) | 2019.09.24 |
| [k-Center Problem] 문제 정의 (0) | 2019.08.16 |
