[스키 대여 문제 / Ski Rental Problem] 선형 계획법을 이용한 Randomized Algorithm

스키 대여 문제(ski rental problem)에 대해서 잘 모르시는 분들은 이 글을 읽기 전에 이전 포스트를 읽어 보시는 것을 추천드립니다.

2020/03/15 - [온라인 알고리즘/Ski rental problem] - [스키 대여 문제 / Ski rental problem] 문제 정의 & break-even algorithm

[스키 대여 문제 / Ski rental problem] 문제 정의 & break-even algorithm

이전 포스트에서는 스키 대여 문제를 정의하고 이를 해결하는 간단한 deterministic 2-competitive algorithm을 제시하였습니다. 마지막으로 deterministic algorithm으로는 2의 경쟁비(competitive ratio)를 가지는 게 최선이라는 것까지 함께 보였습니다.

 

하지만 여전히 우리에게는 돌파구가 있습니다. 바로 알고리즘에 randomness를 도입하는 것이죠. 그러면 대개 더 좋은 성능을 "기대"할 수 있게 됩니다. 과연 이 문제에서는 어떻게 될까요? 놀랍게도 \(B\)가 충분히 큰 경우에는 \(\frac{e}{e-1}\)의 경쟁비를 갖는 알고리즘을 얻을 수 있게 됩니다. 이번에 함께 공부해 보시죠.

선형 계획법 쌍대성을 이용한 deterministic 2-competitive algorithm

이전 포스트에서 소개해드린 알고리즘은 동작도 간단하고 분석도 간결하였습니다. 하지만 제가 이번에 소개할 randomized algorithm을 분석하기 위해서는 그것보다 훨씬 복잡한 기법이 필요합니다. 바로 선형 계획법의 쌍대성(linear programming duality)입니다. 이와 관련된 내용은 이전 포스트에서 자세히 다루었습니다.

2019/07/15 - [수학적 도구/Linear programming] - [선형 계획법] 쌍대성(Duality)

[선형 계획법] 쌍대성(Duality)

사실 쌍대성을 다룬 저 포스트는 다른 글을 쓸 때 도움이 될까봐 꽤 오래전에 적었습니다. 그런데 하도 글을 적지 않다 보니 쌍대성을 활용한 알고리즘이나 분석을 한 적이 없어서 외따로 남겨졌었습니다. 이번에야말로 쌍대성을 활용한 분석을 할 수 있어서 다행으로 생각하고 있습니다.

 

각설하고, 이 기법을 곧바로 적용하여 randomized algorithm을 분석하기 보다는 먼저 이 기법에 익숙해지는 시간을 가지고자 합니다. 격렬한 운동을 하기 전에 준비 운동을 철저히 하는 것처럼 말이죠. 하여, 이 절에서는 쌍대성을 활용한 2-competitive algorithm을 보여드리고자 합니다. 참고로 여기서 제시하는 알고리즘이 저번 포스트에서 나온 간단한 알고리즘(break-even algorithm)과 실제로는 다를 게 없다는 것을 알려 드립니다. 그저 분석의 방법이 훨씬 복잡해졌을 뿐입니다.

 

많은 조합론적 최적화 문제들이 그렇듯이 이 문제도 간단한 정수 선형 계획법(integer linear programming, ILP)으로 표현할 수 있습니다. 바로 온라인 환경을 고려하기에 앞서서 스키장이 \(t^\circ\) 번째 날까지 운영한다고 가정하겠습니다. 우리가 결정해야 할 것은 \(t\) 번째 날(단, \(t \leq t^\circ\))에 스키 장비를 대여할 것인지 아니면 스키를 구매할 것인지입니다. 먼저 \(t\) 번째 날에 장비를 대여했는지를 알려주는 변수를 \(z_t\)라고 하겠습니다. 그날 장비를 대여하면 \(z_t := 1\), 그렇지 않으면 \(z_t := 0\)의 값을 갖습니다. 장비는 한 번 구매하면 계속 쓸 수 있으므로 변수 하나만 두어도 충분할 것입니다. 이는 변수 \(x\)를 두어 장비를 구매하면 \(x := 1\), 아니면 \(x := 0\)으로 표현하도록 하겠습니다.

 

이제 우리 문제에 알맞는 선형 제약 조건(linear constraint)을 구성해야 합니다. 이 문제에서 우리가 반드시 지켜야 하는 것은 무엇일까요? 네, 우리는 매일 스키를 탈 것이므로 대여 장비든 구매한 장비든 매일 둘 중 하나는 갖추어야 합니다. 이는 모든 \(t \leq t^\circ\)에 대해서 \[ x + z_t \geq 1 \]로 나타낼 수 있습니다. 마지막으로 우리 문제에 맞는 목적 함수(objective function)를 알아보도록 하겠습니다. 이것도 간단합니다. 만약 장비를 구매하면 \(B\)의 비용이 발생하고, 반대로 \(t\) 번째 날에 장비를 대여하면 \(1\)의 비용이 발생하므로, 우리는 목표를 \[Bx + \sum_{t \leq t^\circ} z_t\]를 최소화(minimize)하는 것으로 표현할 수 있습니다.

 

이를 모두 조합하면 언제 스키장이 문을 닫는지 미리 알 때의 문제를 다음과 같이 표현할 수 있습니다.

\[ \begin{array}{lrll} \text{minimize } & Bx + \sum_{t \leq t^\circ} z_t & & \\ \text{subject to } & x + z_t & \geq 1, & \forall t \leq t^\circ, \\ & x & \in \{0, 1 \}, & \\ & z_t & \in \{0, 1 \}, & \forall t \leq t^\circ. \\ \end{array} \]

하지만 안타깝게도 ILP는 풀기 어렵다고 알려져 있습니다. 그 이유는 바로 정수 조건 때문인데요. 따라서 정수 조건을 다음과 같이 완화(relax)해 주는 경우가 많습니다.

\[ \begin{array}{lrll} \text{minimize } & Bx + \sum_{t \leq t^\circ} z_t & & \\ \text{subject to } & x + z_t & \geq 1, & \forall t \leq t^\circ, \\ & x & \geq 0, & \\ & z_t & \geq 0, & \forall t \leq t^\circ. \\ \end{array} \]

여기서 굳이 \(x \leq 1\)과 \(z_t \leq 1\) 조건을 넣지 않은 이유는 위 program의 특성 상 필요가 없기 때문입니다.(왜 그럴까요?)

 

본론으로 돌아와서, 이 절 서두에 제가 위에서 제시한 알고리즘을 선형 계획법의 쌍대성을 활용하여 분석해보겠다고 말씀드렸습니다. 그러니 이 program을 primal program으로 하고 그것의 dual program을 가지고 옵시다. 어떻게 만드는지는 굳이 보여드리지 않겠습니다. 제가 쓴 쌍대성 포스트를 잘 읽고 따라하시면 충분히 다음과 같은 dual program을 얻으실 수 있을 것입니다.

\[ \begin{array}{lrll} \text{maximize } & \sum_{t \leq t^\circ} y_t & & \\ \text{subject to } & \sum_{t \leq t^\circ} y_t & \leq B, & \\ & y_t & \leq 1, & \forall t \leq t^\circ, \\ & y_t & \geq 0, & \forall t \leq t^\circ. \\ \end{array} \]

여기서 이 dual program의 첫 번째 제약 조건은 primal program의 \(x\)와 연관되며 두 번째 제약 조건은 \(z_t\)에 연관됩니다.

 

하지만 원래는 온라인 문제였습니다. 따라서 알고리즘의 입장에서 \(t^\circ\)를 알 방법이 없습니다. 때문에 매일매일이 마지막 개장일인 경우에도 알고리즘은 feasible solution을 출력해야 합니다. 그 말인 즉슨, 알고리즘은 첫째 날에 다음의 primal/dual program을 만족해야 합니다.

\[\begin{array}{rl} \begin{array}{lrll} \text{minimize } & Bx + z_1 & & \\ \text{subject to } & x + z_1 & \geq 1, & \\ & x & \geq 0, & \\ & z_1 & \geq 0. & \\ \end{array} & \begin{array}{lrll} \text{maximize } &  y_1 & & \\ \text{subject to } & y_1 & \leq B, & \\ & y_1 & \leq 1, & \\ & y_1 & \geq 0. & \\ \end{array} \end{array}\]

그럼 둘째 날은 어떻게 될까요? 네, \(z_2\)와 \(y_2\)가 새로이 생기면서 primal/dual program이 아래와 같이 갱신되고 알고리즘은 여기에 맞는 solution을 유지해야 합니다.

\[\begin{array}{rl} \begin{array}{lrll} \text{minimize } & Bx + z_1 + z_2 & & \\ \text{subject to } & x + z_1 & \geq 1, & \\ & x + z_2 & \geq 1, & \\ & x & \geq 0, & \\ & z_1, z_2 & \geq 0. & \\ \end{array} & \begin{array}{lrll} \text{maximize } &  y_1 + y_2 & & \\ \text{subject to } & y_1 + y_2 & \leq B, & \\ & y_1 & \leq 1, & \\ & y_2 & \leq 1, & \\ & y_1, y_2 & \geq 0. & \\ \end{array} \end{array}\]

따라서 임의의 \( t^\prime \) 번째 날에는 알고리즘이 매번 다음의 primal/dual program을 고려하고 있다고 생각할 수 있습니다.

\[\begin{array}{rl} P_{t^\prime} := \begin{array}{rrll} \text{minimize } & Bx + \sum_{t \leq t^\prime} z_t & & \\ \text{subject to } & x + z_t & \geq 1, & \forall t \leq t^\prime, \\ & x & \geq 0, & \\ & z_t & \geq 0, & \forall t \leq t^\prime. \\ \end{array} & D_{t^\prime} := \begin{array}{rrll} \text{maximize } & \sum_{t \leq t^\prime} y_t & & \\ \text{subject to } & \sum_{t \leq t^\prime} y_t & \leq B, & \\ & y_t & \leq 1, & \forall t \leq t^\prime, \\ & y_t & \geq 0, & \forall t \leq t^\prime. \\ \end{array} \end{array}\]

이 primal/dual program은 아래에서 요긴하게 사용되니 각각 \(P_{t^\prime}\)과 \(D_{t^\prime}\)이라고 이름을 붙여주도록 하겠습니다.

 

이제 위에서 살펴본 수많은 linear primal/dual program들이 알고리즘을 설계하는데 어떻게 도움이 되는 것일까요? 일단 우리는 알고리즘이 매 \(t^\prime \) 번째 날에 \(P_{t^\prime}\)의 feasible solution \( (x, z) \)를 계속 유지하도록 만들 것입니다. 그것이 원래 우리가 풀려고 한 문제니까 말이죠. 게다가 \( (x, z) \)는 반드시 정수의 값을 가지도록 만들 것입니다. 비록 \( P_{t^\prime} \)에는 정수 제약 조건이 없더라도 정수가 아닌 값은 원래 문제에서 의미가 없어 보입니다. 마지막으로는 알고리즘의 경쟁성(competitiveness)을 위해 \( (x, z) \)의 objective value(즉, \(Bx + \sum_{t \leq t^\prime} z_t\))가 \(\mathsf{OPT}(t^\prime)\)에 비해 그렇게 크지 않도록 할 것입니다.

 

여기서 우리는 경쟁성을 분석할 때 알고리즘의 결과값을 \(\mathsf{OPT}(t^\prime)\)과 직접 비교하지 않고 다른 방식을 취하고자 합니다. 바로 쌍대성을 활용할 것입니다. 좀더 자세히 말하자면, 알고리즘으로 하여금 매 \(t^\prime\) 번째 날에 \( D_{t^\prime} \)의 feasible solution \( y \)를 함께 유지하도록 만들 것입니다. 여기서 중요한 것은 선형 계획법의 weak duality에 의하여 임의의 dual solution의 objective value는 항상 아무 primal solution의 objective value보다 작거나 같다는 사실입니다. 따라서 만약 \( (x, z) \)의 primal objective value가 \( y \)의 dual objective value에 비해 그렇게 크지 않다는 것을 보이면 \(\mathsf{OPT}(t^\prime)\)에 비해서도 그렇게 크지 않음을 유추할 수 있습니다. 즉, \(\mathsf{OPT}(t^\prime)\)을 대신해서 \(y\)의 objective value를 써먹겠다는 의미입니다. 추가로 \(y\)는 굳이 정수의 값을 가질 필요는 없습니다. 어차피 우리에게 중요한 것은 primal program에 feasible 한 정수 solution을 얻는 것이 목표니까요.

 

어떻게 하면 \( (x, z) \)의 objective value가 \( y \)의 dual objective value보다 (그리고 자연히 \(\mathsf{OPT}(t^\prime)\)보다) 그렇게 크지 않도록 \((x, z)\)와 \(y\)를 유지할 수 있을까요? 바로 다음 정리가 그 해답을 제시해 줍니다. 참고로 아래 정리는 optimal primal/dual solution의 필요충분조건인 complementary slackness를 일반화하고 있습니다.

정리 1. Approximate complementary slackness

---

어떤 \(t^\prime\) 번째 날에 대해 그때까지 스키를 타기 위해서 필요한 최소 비용을 \(\mathsf{OPT}(t^\prime)\)이라고 하자. 어떤 상수 \(\rho \geq 1\)에 대해서, \(P_{t^\prime} \)의 feasible primal solution \( (x, z)\)와 \(D_{t^\prime}\)의 feasible dual solution \(y\)가 다음의 조건을 만족한다고 하자.

1. 모든 \(t \leq t^\prime\)에 대해서, 만약 \( y_t > 0\)이면, \(x + z_t \leq \rho \)이다.
2. 만약 \(x > 0\)이면, \( \sum_{t \leq t^\prime} y_t = B \)이다.
3. 임의의 \(t \leq t^\prime \)에 대해, 만약 \(z_t > 0\)이면, \(y_t = 1\)이다.

그러면, \( (x, z) \)의 objective value \( B x + \sum_{t \leq t^\prime} z \)는 \( \rho \mathsf{OPT}(t^\prime)  \)보다 작거나 같다.

[증명] 증명은 complementary slackness의 그것과 상당히 흡사합니다. 다음 식을 고려해봅시다. \[ \sum_{t \leq t^\prime} y_t ( x + z_t ) \] 이는 primal solution과 dual solution의 관계를 생각하면 그렇게 놀라운 것이 아닙니다. 먼저 정리의 조건 1에 의해서 \[ \sum_{t \leq t^\prime} y_t (x + z_t) \leq \rho \sum_{t \leq t^\prime} y_t \leq \rho \mathsf{OPT}(t^\prime) \tag{1} \]을 얻을 수 있습니다. 이때 두 번째 부등식은 \(y\)가 dual feasible solution이라는 점과 weak duality를 통해 이끌어 낼 수 있습니다.

 

처음에 주어진 식을 다음과 같이 정리하면 새로운 등식을 얻을 수 있습니다. \[ \sum_{t \leq t^\prime} y_t (x + z_t) = x \sum_{t \leq t^\prime} y_t + \sum_{t \leq t^\prime} y_t z_t = Bx + \sum_{t \leq t^\prime} z_t \tag{2} \] 여기서 두 번째 등식은 조건 2와 3을 적용하면 어렵지 않게 구할 수 있습니다. 식 1과 2를 조합하면 이 정리가 성립한다는 것을 증명할 수 있습니다. ■

 

지금까지 얻은 아이디어들을 토대로 우리는 다음과 같은 알고리즘을 만들 수 있습니다.

알고리즘 1. A deterministic primal-dual 2-competitive algorithm

---

초기 입력: 스키 장비 구매 비용 \( B \)

출력: 정수 primal feasible solution \( (x, z) \)

 

1. \( (x, z) \gets 0\), \(y \gets 0\)
2. 만일 \(t^\prime\) 번째 날에 스키장이 개장하면 다음을 수행한다.
   1. \(D_{t^\prime}\)의 어떤 제약 조건이 등식을 만족할 때까지 \(y_{t^\prime}\)을 증가시킨다.
      1. 만약 \( \sum_{t \leq t^\prime} y_t = B\)이라면, \(x \gets 1\).
      2. 만약 \( y_{t^\prime} = 1 \)이면, \(z_{t^\prime} \gets 1\).

[증명] 임의의 \(t^\prime\) 번째 날에 대해서 고려하겠습니다. 그 이전의 모든 \(t\) 번째 날(즉, \( t \leq t^\prime \))에 대해서 단계 2가 종료되면 \(x = 1\)이거나 \(z_t = 1\)이 됩니다. 따라서 모든 \(t \leq t^\prime\)에 대해 \(x + z_t \geq 1\)이 만족하므로 \( (x, z) \)는 \(P_{t^\prime}\)의 feasible solution입니다. 또한 \((x, z)\)가 정수의 값만을 갖는다는 것도 그렇게 어렵지 않게 보일 수 있습니다. 따라서 알고리즘의 출력은 올바릅니다.

 

이제 \( (x, z)\)와 \(y\)가 \(\rho = 2\)에 대해 정리 2를 만족한다는 것을 보이도록 하겠습니다. 이것을 성공하면 곧바로 이 알고리즘이 2-competitive 하다는 것을 알 수 있습니다. \( (x, z) \)가 \(P_{t^\prime}\)의 feasible solution이라는 것은 앞에서 보였습니다. \(y\)가 \( D_{t^\prime} \)에 feasible 한지를 따져보면 되는데, 이는 알고리즘의 동작을 통해서 쉽게 이끌어낼 수 있습니다. 단계 2-i을 보면 제약 조건을 어기지 않는 선에서 \(y\)를 변화시키기 때문입니다.

 

마지막으로 정리 2의 세 조건을 만족하는지를 판단하면 됩니다. 먼저 조건 1은 \(x\)든 \(z_t\)든 0 아니면 1의 값을 가질 것이므로 항상 \(x + z_t \leq 2\)입니다. 또한 조건 2와 3은 각각 단계 2-i-a와 2-i-b를 통해서 알고리즘이 강제하고 있다는 것을 확인할 수 있습니다. 이것으로 이 알고리즘이 2-competitive 하다는 것을 증명하였습니다. ■

 

이 절의 도입에도 말씀드렸다시피 이 알고리즘은 사실 저번 글에서 소개한 알고리즘과 똑같이 동작합니다. 만약 \(t^\prime < B\)이면 \(t^\prime\) 번째 날에 \( \sum_{t \leq t^\prime} y_t < B \)가 됩니다. 왜냐면 \(y_t \leq 1\)이기 때문이죠. 따라서 그동안은 단계 2-i-b이 수행되고 이는 \(t^\prime\) 번째 날에 스키 장비를 대여한다는 의미입니다. 하지만, \(t^\prime \geq B\)라면 \( \sum_{t \leq t^\prime} y_t \leq B\)라는 제약 조건에 의해 단계 2-i-a가 수행될 것이고 이는 곧 장비를 구입한다는 뜻이죠.

Fractional \(\frac{e}{e-1}\)-competitive algorithm

Photo by Joseph Greve on Unsplash

알고리즘 1이 갖는 중요한 특징 중 하나는 바로 primal feasible solution \((x, z)\)가 정수로만 이루어져 있다는 것입니다. 사실 deterministic algorithm을 구상하는데 있어서 이는 매우 당연한 처사입니다. 만약 \(x = 0\)이면 스키 장비를 사지 않는 것에 해당하고 반대로 \(x = 1\)이면 스키 장비를 사는 것에 해당합니다. 그럼 \(x = 0.5\)라는 것은 무엇을 의미할까요? 스키 한 짝을 구매하는 것일까요? 물론 변수를 어떻게 정의하느냐에 따라 달라지겠지만, 대개 deterministic algorithm의 세계에서 저러한 fractional value는 의미를 가지기 힘듭니다.

 

하지만 randomized algorithm의 세계에서는 그것들이 의미를 가질 수 있습니다. 예를 들어 \(x = 0.6\)이라면 스키 장비를 60%의 확률로 구매한다는 것을 나타낸다고 볼 수 있습니다. 따라서 이번에는 한 번 \( (x, z)\)가 fractional value로도 이루어질 수 있다고 해보겠습니다. 다만 지금 당장에는 크게 의미 부여를 하지 않도록 하겠습니다. 이를 randomized algorithm과 결부하는 작업은 다음 절에서 보여드리겠습니다.

 

어려운 정수 조건이 없어졌기 때문에 우리에게는 많은 자유가 주어집니다. 예를 들어, \( (x, z) \)가 primal feasible 하기 위해서는 모든 \(t\)에 대해 \(x + z_t \geq 1\)을 만족해야 하는데, 이제는 \(x = 0.3\), \(z_t = 0.7\)과 같은 식으로 채워넣을 수 있다는 것입니다. 이것을 어떻게 활용하면 좋을까요?

 

잠깐 지난 글에서 소개한 break-even algorithm으로 돌아와 보겠습니다. 이 알고리즘의 직관적인 아이디어는 스키장 개장 초기에는 대여를 하는 것이 이득이고 시간이 지남에 따라 점차적으로 장비를 구매하는 것이 이득이 된다는 것입니다. 안타깝게도 그때는 스키 장비를 사거나 사지 않거나, 즉 \(x\)가 0 아니면 1의 값만 취할 수 있기에 어쩔 수 없이 어떤 순간에 \(B\)의 비용을 몽땅 낼 수 밖에 없었습니다.

 

하지만 지금은 fractional value가 허용됩니다. 따라서 초기의 \(t\)에 대해서는 \(x + z_t \geq 1\)에서 \(x\)보다 \(z_t\)에 좀 더 큰 값을 부여하고, 시간이 많이 흐른 후에는 \(z_t\)보다 \(x\)에 더 많은 값을 부여한다면 아마도 더 좋은 경쟁비를 갖는 알고리즘을 만들 수 있을 것입니다. 다음 소개하는 알고리즘에 이 아이디어가 잘 녹아 들어있는 것을 확인하시기 바랍니다.

알고리즘 2. A fractional \(\frac{e}{e-1}\)-competitive algorithm

---

초기 입력: 스키 장비 구매 비용 \( B \)

출력: Primal feasible solution \( (x, z) \)

 

1. \( (x, z) \gets 0\), \(y \gets 0\)
2. 만일 \(t^\prime\) 번째 날에 스키장이 개장하고 \(x < 1\)이면 다음을 수행한다.
   1. \( z_{t^\prime} \gets 1 - x \).
   2. \( x \gets x \left( 1 + \frac{1}{B} \right) + \frac{1}{cB} \).
   3. \( y_{t^\prime} \gets 1 \).

단계 2-ii에 나온 \(c\)는 나중에 정하도록 하겠습니다. 이 알고리즘이 정확하게 동작한다는 것을 보이기 위해서 크게 다음 세 가지를 보이고자 합니다.

정리 2. 알고리즘 2의 특징

---

임의의 \(t^\prime\) 번째 날에 대해 알고리즘 2는 다음을 만족한다.

1. \( (x, z) \)는 \(P_{t^\prime}\)의 feasible solution이다.
2. \(y\)는 \( D_{t^\prime} \)의 feasible solution이다.
3. \(t^\prime\) 번째 날에 알고리즘이 \( \sum_{t \leq t^\prime} y_t\)을 \(1\)만큼 증가시키면, \(Bx + \sum_{t \leq t^\prime} z_t \)는 \( 1 + \frac{1}{c} \)만큼 증가시킨다.

[A 증명] 만약 \(x \geq 1\)이면 자명합니다. 그렇지 않은 경우, 알고리즘의 단계 2-i에 의해서 모든 \(t \leq t^\prime\)에 대해서 \(z_t\)의 값이 설정될 때 \( P_t \)에 feasible 하도록 설정되며, 이후 \(z_t\)의 값은 고정되어 있고 \(x\)의 값은 증가하기만 하므로 \( (x, z) \)는 \(P_{t^\prime}\)에 feasible 합니다. ■

 

정리 2의 B를 증명하기 앞서서 몇 가지를 정의하도록 하겠습니다. 알고리즘 2에서 \(x\)의 값은 1이 되기 전까지 시간이 지남에 따라 계속 증가합니다. 따라서 이를 추적해 보고자 합니다. 모든 \(t\) 번째 날에 대해 알고리즘 2가 단계 2를 수행하고 난 후의 \(x\)의 값을 \(x_t\)라고 부르겠습니다. 자연스럽게 \(x_0\)는 이 알고리즘이 시작할 때의 \(x = 0\)에 해당합니다. 예를 들어, 만약 단계 2-i이 수행되었다면, \(z_t = 1 - x_{t - 1}\)이 될 것입니다.

 

추가로 \(t\) 번째 날에 단계 2에서 \(x\)가 증가한 양을 \(\Delta_t\)라고 하겠습니다. 다시 쓰면, \[ \Delta_t = x_t - x_{t - 1} = \frac{x_{t - 1}}{B} + \frac{1}{cB} \]가 됩니다. 따로 계산해서 보여드리진 않겠지만, \( \Delta_1, \Delta_2, \cdots, \Delta_{t^\prime} \)는 초항이 \( \frac{1}{cB} \)이고 공비가 \( 1 + \frac{1}{B} \)인 등비수열을 이룹니다. 이제 B를 증명해 보겠습니다.

 

[B 증명] 일단 알고리즘이 동작하는 것을 보면 \(y\)가 0 아니면 1로만 이루어져 있다는 것을 쉽게 알 수 있습니다. 따라서 \( \sum_{t \leq t^\prime} y_t \leq B  \)를 만족하는지만 판단하면 됩니다. \(x < 1\)일 때만 단계 2-iii을 통해 \( \sum_{t \leq t^\prime} y_t \)를 1 증가시키기 때문에 아무리 늦어도 \(B\) 번째 날에는 \(x \geq 1\)이 되는 것을 보이면 증명이 됩니다.

 

이것은 \(c\)를 적절하게 골라서 해결할 수 있습니다. 만약 \(B\) 번째 날까지 단계 2-ii가 수행되어 증가가 이루어졌다면 \[ x_B = \sum_{t \leq B} \Delta_t = \frac{(1 + \frac{1}{B})^B - 1}{c}\]가 되는 것을 확인할 수 있습니다. 여기서 두 번째 등식은 등비수열의 합 공식을 통해 유도할 수 있습니다. 만약 우리가 \(c\)를 \[ c = \left(1 + \frac{1}{B} \right)^B - 1\]로 골랐다면 이 알고리즘은 \(B\) 번째 날 이후에는 반드시 \(x\)가 1이 될 것입니다. ■

 

[C 증명] 알고리즘이 \(t^\prime\) 번째 날에 \( \sum_{t \leq t^\prime} y_t \)를 \(1\)만큼 증가시켰다는 것은 단계 2를 시작할 때의 \(x\)(즉, \(x_{t^\prime - 1}\))가 1보다 작은 값이었다는 뜻입니다. 그때 \( Bx + \sum_{t \leq t^\prime} z_t \)의 증가량은 \[ B \Delta_{t^\prime} + z_{t^\prime} = B \left( \frac{x_{t^\prime - 1}}{B} + \frac{1}{cB} \right) + 1 - x_{t^\prime - 1} = 1 + \frac{1}{c} \]이 됩니다. ■

 

이를 모두 조합하면 알고리즘 2가 \( \left( 1 + \frac{1}{c} \right)\)-competitive algorithm임을 보일 수 있습니다.

 

[증명] 명제 A에 의해 알고리즘의 출력이 올바르다는 것을 알 수 있습니다. 명제 B에 의해서 \[ \sum_{t \leq t^\prime} y_t \leq \mathsf{OPT}(t^\prime)\]임을 도출할 수 있습니다. 마지막으로 명제 C에 의해서 \[ Bx + \sum_{t \leq t^\prime} z_t = \left(1 + \frac{1}{c} \right) \sum_{t \leq t^\prime} y_t \]라는 사실도 얻을 수 있습니다. 두 식을 조합하면 원하는 결과를 유도할 수 있습니다. ■

 

충분히 큰 \(B\)에 대해서 \( c = \left( 1 + \frac{1}{B} \right)^B - 1 \approx e - 1\)이 되므로 \( 1 + \frac{1}{c} \approx \frac{e}{e - 1}\)이 되겠습니다.

Randomized algorithm으로 바꾸기

이번 절에서는 드디어 randomized algorithm을 만들어 볼 것입니다. 들어가기 앞서 스키 대여 문제를 해결하는 randomized algorithm이라면 모두 성립하는 사실들을 먼저 짚고 넘어가겠습니다.

 

어떤 알고리즘이 정확히 \(t\) 번째 날에 스키 장비를 구매하는 사건을 \( \mathcal{E}_t \)라고 하고 그 확률을 \(p_t := Pr[\mathcal{E}_t]\)라고 하겠습니다. 여기서 우리는 \(\mathcal{E}_1, \cdots, \mathcal{E}_{t^\prime}\)이 상호 배반(mutually disjoint) 사건들이라는 사실을 알 수 있습니다. 예를 들어 우리가 첫 번째 날에 스키 장비를 구매(\( \mathcal{E}_1 \))했다고 하였을 때, 두 번째 날에 스키 장비를 구매하는 사건(\(\mathcal{E}_2\))은 또 일어나지 않는다는 뜻입니다. 따라서 \(t^\prime\) 번째 날까지 스키 장비를 구매했을 확률을 \(q_{t^\prime}\)라고 했을 때, 이는 \[ q_{t^\prime} := Pr[\mathcal{E}_1 \vee \cdots \vee \mathcal{E}_2] = Pr[\mathcal{E}_1] + \cdots + Pr[\mathcal{E}_{t^\prime}] = \sum_{t \leq t^\prime} p_t \]로 나타낼 수 있습니다.

 

이 사건들을 이용하여 특정 날짜에 스키 장비를 대여하는 확률도 구할 수 있습니다. 만약 \(t^\prime\) 번째 날에 스키 장비를 대여했다는 의미는 첫 번째 날부터 \(t^\prime\) 번째 날까지 장비를 구매하지 않았다는 의미입니다. 따라서 \(t^\prime\) 번째 날에 스키 장비를 대여하는 확률을 \(r_{t^\prime}\)이라고 했을 때, 이 값은 \[ r_{t^\prime} := Pr \left[ \overline{\mathcal{E}_1 \vee \cdots \vee \mathcal{E}_{t^\prime}} \right] = 1 - Pr[ \mathcal{E}_1 \vee \cdots \vee \mathcal{E}_{t^\prime} ] = 1 - \sum_{t \leq t^\prime} p_t \]으로 표현할 수 있습니다.

 

마지막으로 알고리즘이 마지막(\(t^\prime\) 번째 날)에 출력하는 solution의 값을 \( \mathsf{ALG} \)라고 하겠습니다. 이는 알고리즘의 내부 확률 시행에 따라 값이 달라질 수 있는 확률 변수(random variable)입니다. 우리는 위에서 구한 확률을 통해 확률 변수 \(\mathsf{ALG}\)의 기댓값을 다음과 같이 \[ \mathbb{E}[\mathsf{ALG}] = B q_{t^\prime} + \sum_{t \leq t^\prime} r_t \]로 적을 수 있습니다.

 

앞에서 결정 변수의 fractional value는 그것을 선택하는 확률로써 동작할 수 있다고 간략하게나마 언급하였습니다. 이 생각을 확장해, 만약 우리가 위에서 소개한 fractional algorithm의 \( (x, z) \)를 확률로 하는 randomized algorithm을 만들 수 있다면, 그 기댓값이 곧 fractional algorithm의 결과값이 되고, 따라서 같은 경쟁비를 얻어낼 수 있을 것입니다.

 

만약 모든 \(t\)에 대해서 정확히 \(t\) 번째 날에 스키를 구매할 확률이 알고리즘 2에서 \(t\) 번째 날 \(x\)가 증가한 양이 된다면, 다시 말해  \[ p_t = \Delta_t \tag{3} \]가 된다면, 이 알고리즘이 바로 우리가 원하는 알고리즘이 됩니다. 그 이유는 다음과 같습니다. 먼저, \(t^\prime\) 번째 날까지 장비가 구매가 되어있을 확률 \(q_{t^\prime}\)은 알고리즘 2에서 \(t^\prime\) 번째 날을 수행한 후의 \(x\), 즉 \( x_{t^\prime} \)과 동일한 값을 가지게 됩니다. 또한 \(t^\prime\) 번째 날에 장비를 대여하는 확률 \( r_{t^\prime} \)은 \[ r_{t^\prime} = 1 - \sum_{t \leq t^\prime} p_t \leq 1 - \sum_{t \leq t^\prime - 1} \Delta_t = 1 - x_{t^\prime - 1} = z_{t^\prime} \]을 만족하게 됩니다. 따라서 알고리즘이 출력하는 solution의 기댓값은 \[ \mathbb{E}[\mathsf{ALG}] = B q_{t^\prime} + \sum_{t \leq t^\prime} r_t \leq B x_{t^\prime} + \sum_{t \leq t^\prime} z_t \leq \frac{e}{e - 1} \mathsf{OPT}(t^\prime) \]을 만족하게 됩니다.

 

따라서 남은 것은 알고리즘이 식 3을 만족하는 방법을 찾는 것입니다.

알고리즘 3. A randomized \( \frac{e}{e - 1} \)-competitive algorithm

---

초기 입력: 스키 장비 구매 비용 \( B \)

출력: 대여/구매 전략

 

1. 구간 [0, 1)에서 균등한 확률(uniformly at random)로 \(\alpha\)를 고른다.
2. 만일 \(t^\prime\) 번째 날에 스키장이 개장하고 아직 스키를 구매하지 않았으면 다음을 수행한다.
   1. 알고리즘 2를 수행하여 \(x_{t^\prime - 1}\)과 \( x_{t^\prime} \)의 값을 얻는다.
   2. 만약 \(\alpha \in \left[ x_{t^\prime - 1}, x_{t^\prime} \right) \)이면, 스키를 구매한다.
   3. 그렇지 않으면 스키를 대여한다.

[증명] 식 3이 만족함을 보이면 됩니다. 아래 그림을 참고하세요.

그림 1. 알고리즘 3이 식 3을 만족하는 이유의 예시: \(\alpha\)가 3 번째 구간에 들어갈 확률은 \( \Delta_3 \)이다.

균등한 확률로 선택된 \( \alpha \)가 \( \left[ x_{t - 1}, x_t \right) \)에 속할 확률은 \(\Delta_t\)입니다. 따라서 임의의 \(t\)에 대해 \( p_t = \Delta_t \)를 만족합니다. ■

마치며

드디어 스키 대여 문제를 해결하는 randomized \( \frac{e}{e - 1}\)-competitive algorithm을 모두 작성하였습니다. 게다가 이번 글에서는 온라인 알고리즘의 성능을 분석하기 위하여 선형 계획법의 쌍대성을 처음으로 활용해 보았습니다. 여기서 소개된 기법은 비단 스키 대여 문제 뿐 아니라 많은 수의 온라인 알고리즘 및 근사 알고리즘을 디자인하는데 다양하게 활용되고 있습니다. 다음에도 이 기법을 다룬 다른 재미있는 주제를 찾아 포스팅하도록 하겠습니다.

 

참, 컴퓨터과학의 숙명의 질문을 아직 고민하지 않았군요? 과연 \( \frac{e}{e - 1} \)보다 좋은 경쟁비를 갖는 알고리즘을 만들 수 있을까요? 흥미롭게도, 불가능하다고 알려져 있습니다. 혼자서 간단하게 증명을 끄적여 보기는 했는데 스스로 확신이 들지 않아서 이번에 정리하지는 않았습니다. 개인적으로는 그 증명도 선형 계획법의 쌍대성으로 보일 수 있을 것 같은데 혼자서 완벽하게 증명하든 다른 논문에서 발견하든 알게 되면 나중에 정리해 보도록 하겠습니다.

 

항상 글을 작성하면서 느끼는 것은 글의 길이가 처음에 생각했던 것보다 곱절은 많다는 것입니다. 그래서 시작할 때는 "뭐, 이 정도는 곧장 하겠지?"라고 쉽게 생각하고 덤볐다가, 나중에는 "와, X 됐다."라며 진저리 치게 되죠. 그래도 막상 글을 이렇게 정리하고 나니 매우 뿌듯합니다. 아무튼 긴 글을 읽어 주셔서 고맙습니다.

참조 문헌

[1] Niv Buchbinder, Kamal Jain, and Joseph (Seffi) Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In Algorithms – ESA 2007 253-264, 2007.

 

[2] Niv Buchbinder and Joseph (Seffi) Naor. The design of competitive online algorithms via a primal–dual approach. Foundations and Trends® in Theoretical Computer Science 3(2–3):93-263, 2009.