상관없는 기계에서 가중치 완성 시간 최소화하기 (Minimizing Weighted Completion Time on Unrelated Machines)
한 회사에서 어떤 작업들을 처리해야 한다고 합시다. 이 작업들을 처리하기 위해 기계 수 대를 갖고 있습니다. 각 기계들은 회사가 성장해 가면서 하나씩 사들이는 바람에 제원이나 사양이 모두 다릅니다. 다만, 모든 기계는 한 번에 하나의 작업만을 처리할 수 있으며, 한 작업이 시작되면 이를 중단하지 않고 끝까지 처리합니다. 회사 내에서 거의 유일하게 머리 좀 쓰는 공돌이인 여러분은 기계를 활용하여 작업들을 적절히 처리하라는 지시를 받았습니다.
지시 사항을 전달 받은 여러분은 상사에게 곧장 되물었습니다. 목표가 무엇인가요? 기계의 수행 시간을 최소화해야 하는지, 마감 기한을 어기는 정도를 최소화해야 하는지, 아니면 전기비 절감을 위해 기계가 사용하는 에너지를 최소화해야 하는지 등 작업 스케줄을 평가하는 요소는 다양하며, 어떤 평가 척도를 가지냐에 따라 이를 구하는 알고리즘도 달라지기 때문입니다. 이에 상사는 작업마다 중요도가 다르고, 따라서 중요한 작업이 일찍 끝나도록 작업을 처리해 달라고 요청하였습니다. 과연 어떻게 작업을 기계들에 스케줄해야 상사의 요청에 부합할 수 있을까요?
이번 포스트에는 중요도가 다른 작업들과 이를 처리하기 위해 상관없는 기계들(unrelated machines)이 주어질 때, 중요도에 따라 가중된 완성 시간(weighted completion time)의 합을 최소화하는 문제를 근사적으로 해결해 보도록 하겠습니다. 특히, 이번에 소개하는 근사 알고리즘은 준정부호 계획법(semi-definite programming, SDP)을 활용하여 1.5의 근사비를 얻습니다. 개인적으로 예전부터 SDP를 활용하는 근사 알고리즘을 포스팅하고 싶었는데, 이번에 적절한 결과를 공부해서 곧장 정리해 봅니다.
문제 정의
문제부터 정의해 봅시다. 우리에게는 처리해야 하는 \(n\) 개의 작업의 집합 \(J = \{1, 2, \ldots, n\}\)이 주어집니다. 각 작업 \(j \in J\)는 그것의 중요도를 나타내는 가중치 \(w_j \in \mathbb{Q}_+\)가 정해집니다. 모든 작업은 처음부터 다 주어집니다.
작업들을 처리하기 위해 추가로 하나의 작업만 비선점적(non-preemptive)으로 처리하는 상관없는 기계의 집합 \(M\)이 주어집니다. 비선점적이라는 뜻은 한 작업을 처리하는 중에 이를 중단하고 다른 작업을 처리한 후 다시 원래 작업에 되돌아오는 것이 불가능하다는 말이며, 상관없다는 뜻은 기계의 제원이나 성능이 서로 다를 수 있어 어떤 작업의 수행 시간이 기계마다 달라질 수 있다는 의미입니다.
어떤 작업 \(j \in J\)를 어떤 기계 \(i \in M\)에서 처리하는데 필요한 수행 시간은 \(p_{i, j} \in \mathbb{Q}_+\)로 주어집니다. 여기서 기계가 서로 상관없기 때문에 어떤 작업 \(j\)를 기계 \(i\)에서 돌릴 때와 기계 \(i'\)에서 돌릴 때의 수행시간이 \(p_{i, j}\)와 \(p_{i', j}\)로 서로 다를 수 있다는 것을 확인하시기 바랍니다.
어떤 기계 \(i\)에 할당된 작업을 \(j^{(i)}_1, \ldots, j^{(i)}_{\ell_i}\)라고 하고, \(i\)가 이 순서대로 작업들을 처리한다고 해 보겠습니다. 그러면 \(t = 1, \ldots, \ell_i\)에 대해, 작업 \(j^{(i)}_t\)가 완료되는 시각은 정확히 자신을 포함하여 이전에 처리된 모든 작업들의 기계 \(i\)에서의 수행 시간의 합, 즉, \[ \sum_{t' = 1}^t p_{i, j^{(i)}_{t'}} \]이 될 것입니다. 우리는 이를 완성 시간이라고 부릅니다. 모든 작업들이 할당되었을 때 어떤 작업 \(j \in J\)의 완성 시간을 \(C_j\)라고 부르겠습니다.
문제의 목표는 작업을 기계에 모두 할당하면서 가중치가 곱해진 완성 시간의 합, 즉, \[\sum_{j \in J} w_j C_j\]의 값을 최소화하는 작업의 스케줄을 찾는 것입니다. 직관적으로 말해, 이 목적 함수를 줄이기 위해서는 가중치가 큰 중요한 작업들을 처리해야 하겠습니다.
기계가 하나일 때 ― 스미스 비율
본론에 들어가기 전에 하나의 기계만 있을 때를 고려해 보겠습니다. 기계가 하나뿐이므로 각 작업 \(j \in J\)에 대해, 그것의 수행 시간을 \(p_j\)라고 나타내겠습니다. 흥미롭게도 이 경우에는 이 문제를 최적으로 해결하는 간단한 탐욕 알고리즘(greedy algorithm)이 존재합니다.
작업을 단위 시간 당 가중치, 즉, \(w_j / p_j\)의 내림차순으로 정렬하고 그 순서대로 처리한다.
단위 시간 당 가중치가 큰 것을 먼저 처리하는 것이 이득이 된다는 것은 직관적으로 받아들일 수 있다고 생각합니다. 엄밀한 증명도 아래와 같이 교환 논의(exchange argument)를 활용하면 어렵지 않게 보일 수 있습니다.
정리 1. 알고리즘의 정당성
이 알고리즘이 출력하는 스케줄의 가중된 완성 시간의 합은 최소이다.
[증명] 일반성을 잃지 않고 작업을 알고리즘이 스케줄한 순서대로 \(1, \ldots, n\)이라고 다시 이름을 붙이겠습니다. 따라서, \[w_1 / p_1 \geq w_2 / p_2 \geq \ldots \geq w_n / p_n\]을 만족합니다.
가중된 완성 시간의 합을 최소로 하는 스케줄을 하나 고정하고 이를 \(O\)라고 부르겠습니다. 이 스케줄에서는 \(o_1, \ldots, o_n \)의 순서대로 작업을 처리한다고 하겠습니다. 즉, \(t = 1, \ldots, n\)에 대해, \(O\)에서 \(t\) 번째로 수행되는 작업은 \(o_t\)입니다. 만약 \(o_t = t\)라면 이는 곧 알고리즘의 출력과 동일하므로 더 이상 증명할 것이 없습니다.
따라서 알고리즘의 출력에서의 순서와 \(O\)에서의 순서가 다른 쌍, 즉, \(s < s'\)이지만 \(o_s > o_{s'}\)인 \(s, s' \in \{1, \ldots, n\}\)이 존재한다고 해 보겠습니다. 이러한 \(s, s'\)이 존재하면, 분명 \(o_t > o_{t + 1}\)인 \(t \in \{1, \ldots, n - 1\}\)도 존재하여야 합니다. 그렇지 않다면 \(o_s \leq o_{s + 1} \leq \cdots \leq o_{s'}\)가 되어 \(s, s'\)의 존재성에 모순을 일으키기 때문입니다.
이제 다른 작업의 순서는 그대로 두고 \(o_t\)와 \(o_{t + 1}\)의 순서만 바꾼 스케줄 \(O'\)을 생각해 보겠습니다. 서로 인접한 두 작업의 순서를 바꾸었으므로 다른 작업들의 완성 시간은 변함이 없습니다. 정확히 \(O\)에서는 \(t\) 번째에 수행된 작업인 \(o_t\)가 \(O'\)에서는 \(t+1\) 번째에 수행이 되며, 반대로 \(t + 1\) 번째 작업인 \(o_{t + 1}\)은 \(t\) 번째에 수행이 되어 각각의 완성 시간이 바뀝니다.
\(O\)와 \(O'\)에서 \(t-1\) 번째 작업까지 완료하는데 걸리는 시간, 즉 \(o_{t-1}\)의 완성 시간을 \(C\)라고 하겠습니다. (만약 \(t = 1\)이라면 \(C = 0\)으로 정의합니다.) 그러면 \(O\)에서 \(o_t\)와 \(o_{t + 1}\)의 가중된 완성 시간을 합한 값은 \[ w_{o_t} (C + p_{o_t}) + w_{o_{t + 1}} (C + p_{o_t} + p_{o_{t + 1}}) \]이 됩니다. 반면 \(O'\)에서는 \[ w_{o_{t + 1}} (C + p_{o_{t + 1}}) + w_{o_t} (C + p_{o_{t + 1}} + p_{o_t}) \]가 될 것입니다.
아래 식에서 위 식을 빼면 우리는 \[ w_{o_{t + 1}} p_{o_t} - w_{o_t} p_{o_{t + 1}} = p_{o_t} p_{o_{t + 1}} \left( \frac{w_{o_{t + 1}}}{p_{t + 1}} - \frac{w_{o_t}}{p_{o_t}} \right) \leq 0 \]이 되어 \(O'\)에서의 가중된 완성 시간의 합이 \(O\)보다 크지 않음을 보일 수 있습니다. 이때, 마지막 부등식은 \(o_t > o_{t + 1}\)이라서 \(w_{o_t}/p_{o_t} \leq w_{o_{t + 1}} / p_{o_{t+1}}\)가 되기 때문에 성립합니다.
위의 교환 작업을 진행하면 알고리즘의 출력에서의 순서와 다른 쌍의 개수가 줄어들게 됩니다. 따라서 위 작업을 계속 진행하면 언젠간 알고리즘의 출력과 동일해지며, 매번 작업을 진행할 때 목적 함수의 값이 증가하지 않음을 보였으므로 알고리즘의 출력은 최적입니다. ■
이렇게 알고리즘에서 핵심적인 역할을 하는 단위 시간 당 가중치를 스미스 비율(Smith's ratio)이라고 부릅니다.
정수 이차 계획법과 준정부호 계획법 완화
이제 상관없는 기계가 여러 대 존재하는 일반적인 경우를 생각해 보겠습니다. 이전 절에서 유추할 수 있는 사실은 작업들을 각 기계에 어떻게 분배할지만 정해 준다면 각각의 기계에 할당된 작업들의 처리 순서를 스케줄하는 것은 스미스 비율에 따르면 된다는 점입니다.
이를 수리 계획법(mathematical programming)으로 표현해 보겠습니다. 어떤 기계 \(i \in M\)에 대해, 만약 \(j\)의 스미스 비율이 \(j'\)의 그것보다 크거나 같다면, 즉, \(w_j/p_{i, j} \geq w_{j'} / p_{i, j'}\)이라면, 우리는 이를 \[ j \preceq_i j' \]이라고 표기하겠습니다. 이는 \(j\)와 \(j'\)이 동시에 \(i\)에 할당되었을 때, \(j\)가 \(j'\)보다 먼저 처리되어야 하는 것을 나타냅니다. \(\preceq_i\)로 표현되는 우선순위가 전순서(total order)를 이룬다고 가정하겠습니다. 만약 동률(tie)이 있다면, 이는 아무렇게 그렇지만 일관되게 처리해 주면 됩니다.
이제 각각의 기계 \(i \in M\)와 작업 \(j \in J\)에 대해, 0 아니면 1의 값을 갖는 결정 변수 \(x_{i, j}\)를 만들겠습니다. 이는 만약 \(i\)가 \(j\)에 할당되었을 때 1의 값을, 그렇지 않으면 0의 값을 갖는다고 해석할 것입니다. 그러면 우리는 이 문제를 다음과 같은 정수 이차 계획법(integer quadratic programming)으로 표현할 수 있습니다.
\[\begin{array}{lrl} \text{minimize } & \displaystyle \sum_{i \in M} \sum_{j \in J} w_j \left[ \sum_{j' \in J : j' \preceq_i j} p_{j'} x_{i, j'} x_{i, j} \right] & \\ \text{subject to } & \displaystyle \sum_{i \in M} x_{i, j} = 1, & \forall j \in J, \\ & x_{i, j} \in \{0, 1\}, & \forall i \in M, j \in J. \end{array} \tag{QP} \]
첫 번째 제약 조건(constraint)은 모든 작업이 정확히 하나의 기계에 포함되어야 한다는 것을 의미합니다. 이제 목적 함수가 정확히 우리가 원하는 가중된 완성 시간의 합을 표현하는지를 살펴 보겠습니다. 각 \(i \in M\), \(j \in J\)에 대해서, \(j\)가 \(i\)에 할당되면 \(x_{i, j} = 1\)의 값을 가질 것입니다. 이때 \(j\)의 완성 시간을 구하기 위해서는 \(j\)를 포함해 \(i\)에 할당된 \(j\)보다 스미스 비율이 작지 않은 작업 \(j'\)이 무엇인지 알면 됩니다. 이는 곧 \(j' \preceq_i j\)이면서 \(x_{i, j'} = 1\)인 \(j'\)이며, 따라서 \[C_j = \sum_{j' \in J : j' \preceq_i j} p_{j'} x_{i,j'} x_{i, j}\]가 성립합니다. 이로써 위의 정수 이차 계획법 문제는 원래 풀고자 하는 문제를 잘 표현하고 있음을 알 수 있습니다.
정수 선형 계획법 문제의 정수 조건을 완화하여 선형 계획법 완화(linear programming relaxation)를 구하는 것은 많은 근사 알고리즘의 시작점입니다. 문제 QP도 똑같은 방식으로 정수 조건을 완화해 보겠습니다. 다만 여전히 한 가지 문제가 있는데, 목적 함수가 두 변수의 곱으로 표현되는 항이 있는 이차 함수라는 것입니다. 일반적으로 이차 계획법은 정수 조건이 없어도 다항 시간에 풀기 어렵다고 알려져 있습니다.
따라서 다항 시간에 해결하기 위해 우리는 이 문제를 선형화하는 작업이 필요합니다. 이를 위해 각 \(i \in M\), 그리고 두 작업 \(j, j' \in M\)에 대해, \(x_{i,j \cup i, j'}\)이라는 결정 변수를 만들어 보겠습니다. 이것의 의미는 기계 \(i\)에 작업 \(j\)와 \(j'\)이 함께 할당된 것을 나타냅니다. 참고로 위 정의에서 \(j = j'\)일 수도 있습니다. 이때는 의미 상 \(x_{i, j \cup i, j} = x_{i, j}\)로 해석하는 것이 자연스럽습니다.
이렇게 정의한 \( \{x_{i, j \cup i, j'}\}_{i \in M, j, j' \in J} \)를 이용하면 문제 QP의 목적 함수를 \[ \sum_{i \in M} \sum_{j \in J} w_j \left[ \sum_{j' \in J : j' \preceq_i j} p_{j'} x_{i, j' \cup i, j} \right]\]로 적을 수 있습니다. 이제 남은 과제는 \(x_{i, j \cup i, j'}\)이 우리가 의도한 대로 \(j\), \(j'\)이 동시에 할당되는 것을 표현하도록 적절한 제약 조건을 추가하는 것입니다. 하지만 본디 이차식이었기에 선형 제약 조건만으로는 이를 표현는 것은 쉽지 않아 보입니다.
이를 위해 준정부호 계획법(semi-definite programming, SDP)을 대신 사용해 보고자 합니다. 이 방법을 이해하기 위해서는 다음의 정의와 성질을 알아야 합니다. 증명은 생략하겠습니다.
정의 1. 양의 준정부호 행렬
어떤 행렬 \(A \in \mathbb{R}^{n \times n}\)이 임의의 벡터 \(v \in \mathbb{R}^n \)에 대해, \(v^\intercal A v \geq 0\)을 만족하면, 우리는 \(A\)를 양의 준정부호 행렬(positive semi-definite matrix)이라고 부르며, 기호로는 \(A \succeq 0\)으로 표현한다.
정리 2. 양의 준정부호 행렬의 필요충분조건
어떤 행렬 \(A \in \mathbb{R}^{n \times n}\)이 양의 준정부호 행렬일 필요충분조건은 \(B B^\intercal = M\)인 어떤 행렬 \(B \in \mathbb{R}^{n \times m}\)이 존재하는 것이다.
이 개념이 어떻게 도움이 되는지 알아 보겠습니다. 어떤 정수 계획법 문제를 완화한다는 것은 꼭 정수 조건을 실수 조건으로 갈아 끼우는 것만 뜻하지 않습니다. 좀더 정확히는 원래 문제의 모든 정수해(integral solution)가 완화된 문제의 가능한 해(feasible solution)이면 됩니다. 문제 QP의 임의의 정수해 \(\{x_{i, j} \}_{i \in M, j \in J}\)를 생각해 보겠습니다. 그리고 이를 선형화하기 위해서 도입했던 \( \{x_{i, j \cup i, j'}\}_{i \in M, j, j' \in J} \)에 확장을 시켜 보겠습니다. \(x_{i, j \cup i, j'} = 1\)의 의미는 \(i\)에 \(j\)와 \(j'\)이 동시에 할당되었다는 것입니다. 따라서 \(x_{i, j}, x_{i, j'}, x_{i, j \cup i, j'}\)이 모두 0 또는 1의 값만 갖는다면, \[ x_{i, j \cup i, j'} = x_{i, j} x_{i, j'} \]이 만족할 것입니다. 같은 이치로 \(x_{i, j}\)가 0 또는 1만을 갖기 때문에 \[ x_{i, j}^2 = x_{i ,j} \]가 됩니다.
이제 임의의 기계 \(i \in M\)에 대해, \(A^{(i)}\)를 지금까지 정의한 결정 변수들을 가지고 다음과 같이 정의해 보겠습니다.
\[ A^{(i)} := \begin{bmatrix} 1 & x_{i, 1} & x_{i, 2} & \cdots & x_{i, n} \\ x_{i, 1} & x_{i, 1} & x_{i, 1 \cup i, 2} & \cdots & x_{i, 1 \cup i, n} \\ x_{i, 2} & x_{i, 1 \cup i, 2} & x_{i, 2} & \cdots & x_{i, 2 \cup i, n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x_{i, n} & x_{i, 1 \cup i, n} & x_{i,2 \cup i, n} & \cdots & x_{i, n} \end{bmatrix}. \]
만약 \(\{x_{i, j}\}_{i \in M, j \in J} \cup \{x_{i, j \cup i, j'}\}_{i \in M, j, j' \in J}\)가 0 또는 1로만 이루어진 정수해라면, 앞에서 얻은 수식들을 통해 우리는
\[A^{(i)} = \begin{bmatrix} 1 & x_{i, 1} & x_{i, 2} & \cdots & x_{i, n} \\ x_{i, 1} & x^2_{i, 1} & x_{i, 1} x_{i, 2} & \cdots & x_{i, 1} x_{i, n} \\ x_{i, 2} & x_{i, 1} x_{i, 2} & x^2_{i, 2} & \cdots & x_{i, 2} x_{i, n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x_{i, n} & x_{i, 1} x_{i, n} & x_{i,2} x_{i, n} & \cdots & x^2_{i, n} \end{bmatrix} = \begin{bmatrix} 1 \\ x_{i, 1} \\ x_{i, 2} \\ \vdots \\ x_{i, n} \end{bmatrix} \begin{bmatrix} 1 & x_{i, 1} & x_{i, 2} & \cdots & x_{i, n} \end{bmatrix} \succeq 0\]을 이끌어낼 수 있습니다. 이때 마지막에 \(X^{(i)}\)가 양의 준정부호 행렬이 되는 이유는 정리 2의 필요충분조건에서 알 수 있습니다.
위 논의를 통해서 우리는 다음의 문제가 문제 QP의 적절한 완화라는 것을 알 수 있습니다.
\[\begin{array}{lrl} \text{minimize } & \displaystyle \sum_{i \in M} \sum_{j \in J} w_j \left[ \sum_{j' \in J : j' \preceq_i j} p_{j'} x_{i, j' \cup i, j} \right] & \\ \text{subject to } & \displaystyle \sum_{i \in M} x_{i, j} = 1, & \forall j \in J, \\ & A^{(i)} \succeq 0, & \forall i \in M, \\ & x_{i, j}, x_{i, j \cup i, j'} \geq 0, & \forall i \in M, j, j' \in J. \end{array} \tag{REL} \]
위와 같이 양의 준정부호 행렬 조건이 있는 문제를 우리는 SDP라고 부릅니다. 일반적으로 SDP는 아주 약간의 오차를 허용하면 다항 시간에 해결할 수 있음이 알려져 있습니다.
1.5-근사 알고리즘
이제 상관없는 기계에서 가중치 완성 시간의 합을 최소화하는 문제를 해결하는 1.5-근사 알고리즘을 소개하겠습니다. 이 알고리즘은 다음의 세 단계로 쉽게 설명할 수 있습니다.
- 문제 REL을 해결하여 최적해 \(x\)를 얻는다.
- 각 작업 \(j \in J\)에 대해 독립적으로 기계 \(i \in M\)을 \(x_{i, j}\)의 확률로 고르고 \(j\)를 \(i\)에 할당한다.
- 각 기계 \(i \in M\)에 할당된 작업들을 스미스 비율에 따라 정렬하여 처리한다.
이 알고리즘은 다항 시간에 동작합니다. 또한 모든 작업이 하나의 기계에 할당되고, 각 기계에 할당된 작업들의 순서도 정하였으므로 알고리즘은 올바른 스케줄을 출력합니다.
따라서 이제 남은 것은 알고리즘의 출력이 최적값의 1.5 배를 넘지 않는다는 것을 보이는 것입니다. 이를 위해 몇 가지 정의가 또 필요합니다. 각 기계 \(i \in M\)와 작업 \(j \in J\)에 대해, \(X_{i, j}\)를 알고리즘이 \(j\)를 \(i\)에 할당하였을 때 1, 그렇지 않으면 0의 값을 갖는 확률 변수라고 하겠습니다. \(\mathsf{ALG}\)를 알고리즘 출력의 목적 함수의 기댓값이라고 하면, 우리는
\[ \mathsf{ALG} = \mathbb{E} \left[ \sum_{i \in M} \sum_{j \in J} w_j \left[ \sum_{j' \in J : j' \preceq_i j} p_{j'} X_{i, j'} X_{i, j} \right] \right] \]
임을 알 수 있습니다. 기댓값의 선형성(linearity of expectation)에 의해 \(\sum_{i \in M}\)을 기댓값의 바깥으로 꺼내면 \(\mathsf{ALG}\)는 곧 아래 정의된 \(\mathsf{ALG}_i\)의 합으로 표현될 수 있습니다.
\[\mathsf{ALG}_i := \mathbb{E} \left[ \sum_{j \in J} w_j \left[ \sum_{j' \in J : j' \preceq_i j} p_{j'} X_{i, j'} X_{i, j} \right] \right]. \tag{1} \]
비슷한 원리로 알고리즘의 단계 1에서 문제 REL을 해결해 얻은 최적해의 목적 함수 값도 아래의 \(\mathsf{REL}_i\)의 합으로 표현할 수 있습니다.
\[ \mathsf{REL}_i := \sum_{j \in J} w_j \left[ \sum_{j' \in J : j' \preceq j} p_{j'} x_{i, j' \cup i, j} \right]. \tag{2} \]
문제 REL은 원래 문제의 적절한 완화이므로 만약 우리가 각 기계 \(i \in M\)에 대해,
\[\mathsf{ALG}_i \leq 1.5 \cdot \mathsf{REL}_i \]
을 보일 수 있다면, 이 알고리즘은 1.5-근사 알고리즘이 될 것입니다.
이제부터 어떤 기계 \(i \in M\)을 하나 고정하고, 편의 상 \(i\)를 모두 생략하겠습니다. 예를 들어, \(p_j := p_{i, j}\), \(p_{j' \cup j} := p_{i, j \cup i, j'}\), \(X_{j} := X_{i, j}\), \(x_j := x_{i, j}\), \(x_{j' \cup j} := x_{i, j' \cup i, j}\)로 표현하겠습니다. 각 작업 \(j \in J\)의 기계 \(i\)에서의 스미스 비율을 \(\beta_j := w_j / p_j \)라고 하겠습니다. 일반성을 잃지 않고 \(J = \{1, \ldots, n\}\)이 \( \beta_1 \geq \beta_2 \geq \cdots \geq \beta_n\)을 만족하도록 이름을 다시 붙이겠습니다.
정리 3. \(\mathsf{ALG}_i\)와 \(\mathsf{REL}_i\)의 다른 표현
아래의 두 식이 성립한다. 단 \(\beta_{n + 1} := 0\)이다.
- \( \displaystyle \mathsf{ALG}_i = \sum_{j^\circ= 1}^n (\beta_{j^\circ} - \beta_{j^\circ + 1}) \mathbb{E} \left[ \sum_{j = 1}^{j^\circ} \sum_{j' = 1}^j p_{j'} p_j X_{j'} X_j \right]; \)
- \(\displaystyle \mathsf{REL}_i = \sum_{j^\circ = 1}^n (\beta_{j^\circ} - \beta_{j^\circ + 1}) \left[ \sum_{j = 1}^{j^\circ} \sum_{j' = 1}^j p_{j'} p_j x_{j' \cup j} \right]. \)
[증명] 먼저 첫 번째 등식이 성립함을 보이겠습니다. 임의의 \(t \in J\)에 대해, \[S_t := \mathbb{E} \left[ \sum_{t' = 1}^t p_{t'} p_t X_{t'} X_t \right] \]라고 하겠습니다. 그러면 첫 번째 등식의 우변은 \[ \sum_{j^\circ = 1}^n (\beta_{j^\circ} - \beta_{j^\circ + 1}) \sum_{j = 1}^{j^\circ} S_{j} \tag{3} \]와 같습니다.
이제 식 (1)을 살펴 보겠습니다. 스미스 비율 정의에 의해 \(w_j = \beta_j p_j\)를 만족합니다. 그러므로 \(S_t\)의 정의와 함께, \( \mathsf{ALG}_i = \sum_{j = 1}^n \beta_{j} S_j \)와 같이 쓸 수 있습니다. 이 식의 \(\beta_j\)를 굳이 \[ \sum_{j = 1}^n \sum_{j^\circ = j}^n (\beta_{j^\circ} - \beta_{j^\circ + 1}) S_j \]와 같이 풀어 적어 보겠습니다. 이 식에서 덧셈의 순서를 뒤집으면 정확히 식 (3)과 동일함을 보일 수 있습니다.
두 번째 등식은 비슷한 방식으로 식 (2)와 동일함을 보일 수 있으므로 생략합니다. ■
어떤 고정된 작업 \(j^\circ \in J\)에 대해,
\[ \mathsf{ALG}_{i, j^\circ} := \mathbb{E} \left[ \sum_{j = 1}^{j^\circ} \sum_{j' = 1}^j p_{j'} p_j X_{j'} X_j \right], \quad \mathsf{REL}_{i, j^\circ} := \sum_{j = 1}^{j^\circ} \sum_{j' = 1}^j p_{j'} p_j x_{j' \cup j} \]
으로 정의하겠습니다. 만약 \[ \mathsf{ALG}_{i, j^\circ} \leq 1.5 \cdot \mathsf{REL}_{i, j^\circ} \tag{4} \]임을 보이면 우리 알고리즘이 1.5-근사 알고리즘이라는 사실을 증명할 수 있게 됩니다.
먼저 알고리즘의 출력에 대한 적절한 상한을 구해 보겠습니다.
정리 4. \(\mathsf{ALG}_{i, j^\circ}\)의 상한
\( \displaystyle \mathsf{ALG}_{i, j^\circ} \leq \sum_{j = 1}^{j^\circ} x_j p^2_j + \frac{1}{2} \left( \sum_{j =1}^{j^\circ} x_j p_j \right)^2. \)
[증명] 알고리즘은 각 작업 \(j\)에 대해 독립적으로 \( x_{i, j} \)의 확률로 \(i\)에 할당됩니다. 따라서 서로 다른 두 작업 \(j \neq j' \in J\)에 대해 \(\mathbb{E}[X_{j'}X_j] = x_{j'} x_j\)와 동일합니다. 반대로 \(X_j\)는 0 아니면 1의 값을 갖는 확률 변수이므로 \( \mathbb{E}[X^2_j] = \mathbb{E}[X_j] = x_j \)가 성립합니다. 위 사실과 함께 기댓값의 선형성을 \(\mathsf{ALG}_{i, j^\circ}\)의 정의에 적용하면 우리는 \[ \mathsf{ALG}_{i, j^\circ} = \sum_{j = 1}^{j^\circ} \sum_{j' = 1}^{j - 1} p_{j'} p_j x_{j'} x_j + \sum_{j = 1}^{j^\circ} p^2_j x_j \leq \frac{1}{2} \left( \sum_{j = 1}^{j^\circ} x_j p_j \right)^2 + \sum_{j = 1}^{j^\circ} x_j p^2_j \]를 이끌어 낼 수 있습니다. ■
이제 문제 REL의 최적해 \(x\)에 대한 적절한 하한을 얻어 보겠습니다. 두 개의 하한을 얻을 건데, 하나는 간단히 계산할 수 있으나, 다른 하나는 원래 문제가 SDP여서 얻을 수 있습니다.
정리 5. \(\mathsf{REL}_{i, j^\circ}\)의 하한 1
\( \displaystyle \mathsf{REL}_{i, j^\circ} \geq \sum_{j = 1}^{j^\circ} x_j p^2_j. \)
[증명] \(\mathsf{REL}_{i, j^\circ}\)의 정의에서 정확히 \(j = j'\)인 항만 긁어 모으면, \(x_{j \cup j} = x_j\)라고 하였으므로 정리가 곧장 성립합니다. ■
정리 6. \(\mathsf{REL}_{i, j^\circ}\)의 하한 2
\(\displaystyle \mathsf{REL}_{i, j^\circ} \geq \frac{1}{2} \left[ \sum_{j = 1}^{j^\circ} x_j p^2_j + \left( \sum_{j = 1}^{j^\circ} x_j p_j \right)^2 \right]. \)
[증명] 먼저, \[ \mathsf{REL}_{i, j^\circ} = \frac{1}{2} \left( \sum_{j = 1}^{j^\circ} x_j p^2_j + \sum_{j = 1}^{j^\circ} \sum_{j' = 1}^{j^\circ} x_{j \cup j} p_j p_{j'} \right) \]이 되는 것을 확인하시기 바랍니다. 이는 우변의 식을 전개하면 쉽게 보일 수 있습니다. 따라서, 만약 \[ \sum_{j = 1}^{j^\circ} \sum_{j' = 1}^{j^\circ} x_{j \cup j'} p_j p_{j'} \geq \left( \sum_{j = 1}^{j^\circ} x_j p_j \right)^2 \]임을 보인다면, 정리의 명제가 성립합니다. 문제 REL에서 정의했던 \(A := A^{(i)}\)는 양의 준정부호 행렬입니다. 따라서 임의의 \(v \in \mathbb{R}^{n + 1}\)에 대해, \(v^\intercal A v \geq 0\)을 만족합니다. \(A\)의 각 행과 각 열을 현재 고려하고 있는 작업의 순서대로 옮겨 준 후, 다음의 \(v\)를 고려해 봅시다.
\[ v := \begin{bmatrix} - \sum_{j = 1}^{j^\circ} x_j p_j \\ p_1 \\ \vdots \\ p_{j^\circ} \\ 0 \\ \vdots \\ 0 \end{bmatrix}. \]
이를 계산해 보면,
\[ v^\intercal A v = \left( \sum_{j = 1}^{j^\circ} x_j p_j \right)^2 - 2 \cdot \left( \sum_{j = 1}^{j^\circ} x_j p_j \right)^2 + \sum_{j = 1}^{j^\circ} \sum_{j' = 1}^{j^\circ} x_{j \cup j'} p_j p_{j'} \geq 0 \]
가 되어 저희가 원하는 부등식을 얻을 수 있습니다. ■
이를 활용하여 식 (4)를 증명할 수 있습니다. 그리고 이것이 곧 알고리즘이 1.5-근사 알고리즘이라는 증명입니다.
정리 7. 알고리즘의 근사비
\( \mathsf{ALG}_{i, j^\circ} \leq 1.5 \cdot \mathsf{REL}_{i, j^\circ} \).
[증명] \(L := \sum_{j = 1}^{j^\circ} x_j p_j\), \(Q := \sum_{j = 1}^{j^\circ} x_j p^2_j\)이라고 하겠습니다. 정리 4-6을 통해 우리는 \[ \begin{array}{rl} \mathsf{ALG}_{i, j^\circ} & \leq Q + L^2 / 2 \\ \mathsf{REL}_{i, j^\circ} & \geq Q \\ \mathsf{REL}_{i, j^\circ} & \geq (Q + L^2) / 2 \end{array} \]임을 보였습니다. 정리 5와 6의 볼록 조합(convex combination)도 항상 유효한 하한을 이루므로 우리는 \[ \mathsf{REL}_{i, j^\circ} \geq \frac{1}{3} \cdot Q + \frac{2}{3} \cdot (Q + L^2) / 2 = \frac{2}{3} \cdot (Q + L^2 / 2) \geq \frac{2}{3} \mathsf{ALG}_{i, j^\circ} \]임을 이끌어 낼 수 있습니다. ■
마치며
이것으로 상관없는 기계에서 가중된 완성 시간의 합을 최소화하는 문제를 해결하는 1.5-근사 알고리즘에 대한 정리를 마칩니다. 개인적으로 SDP를 활용한 알고리즘들을 유심히 살펴 보고는 했었는데, 이번에 아주 직관적으로 받아 들여지는 결과를 알게 되어 이렇게 정리하여 봅니다.
본문의 결과가 담긴 논문은 1.5-근사 알고리즘을 주는 것에서 끝나지 않습니다. 사실 1.5의 근사비를 갖는 알고리즘은 이전에도 알려져 있었습니다. 대신 1.5보다 좋은 근사비를 갖는 알고리즘이 존재하는지가 열린 문제였다고 합니다. 이 논문은 처음으로 1.5보다 좋은 근사비를 갖는 알고리즘을 제시하였으며 그 결과는 강한 음의 상관관계(strong negative correlation)를 통해 얻을 수 있었습니다.
직관적으로 강한 음의 상관관계가 어째서 도움이 되는지를 간략히 설명해 보겠습니다. 정리 4의 증명을 살펴 보면, \(X_j\)가 모두 독립이어서 \(\mathbb{E}[X_j X_{j'}] = x_j x_{j'}\)을 얻을 수 있었습니다. 그런데 만약 우리가 작업 \(j\)와 작업 \(j'\)이 어떤 기계 \(i\)에 할당되는 사건이 강한 음의 상관관계를 갖는다면, 0보다 큰 어떤 상수 \(\delta\)에 대해 \(\mathbb{E}[X_j X_{j'}] \leq (1 - \delta) x_j x_{j'} \)을 얻을 수 있겠습니다. 이를 통해 정리 4의 우변을 어떤 상수의 인자(factor)만큼 감소시킬 수 있을 것입니다. 최근 이 기법을 더욱 발전시켜 1.4까지 근사비를 낮춘 성과도 발표되었습니다.
다음 번에는 어떻게 하면 작업을 기계에 할당하는 것에 음의 상관관계를 도입할 수 있는지 살펴 보도록 하겠습니다.
읽어 주셔서 고맙습니다.
참고 자료
[1] Nikhil Bansal, Aravind Srinivasan, and Ola Svensson. "Lift-and-round to improve weighted completion time on unrelated machines." In STOC 2016.
[2] David G. Harris. "Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time." To appear in SODA 2024.