Online 알고리즘 (3) - Deterministic Online Algorithms (2)

Maximization Problem: Time Series Search

이번 포스팅에서는 전 포스팅의 Minimization과 대비되는 형태의 문제인 Maximization 문제를 다루도록 하겠습니다. Time Series Search (이하 TSS)문제는 대표적인 maximization 문제입니다. 

 

한 항공사에서 유럽여행 이벤트를 한다고 가정하겠습니다. 이럴 경우는 없겠지만 이 이벤트는 여러분을 n일 후에 유럽으로 공짜로 보내주는 이벤트입니다. 다만 여러분은 n일이 언제인지 모르고 당일날 통보를 받게 됩니다. 이 여행을 가기 위해서 많은 준비를 해야하겠지만 가장 중요한 건 원화를 유로로 바꿔야합니다. 목표는 환율이 여러가지 요인으로 변동하는 상황에서 가장 이득이 되는 날을 골라서 모든 돈을 바꾸는 것입니다. 하지만 만약에 바꾸지 못한다면 항공사에서 정해준 n일뒤에 바꿔야 하는 불상사가 일어날 수 있습니다. 물론 그 날의 환율이 좋다면 괜찮지만 최악일 수도 있습니다. 그렇다면 한번 문제를 정의해보겠습니다.

 

문제의 입력은 $(p_1, p_2, ..., p_n)$, $p_j$는 j번째 날 환율입니다. 1원에 $p_j$달러라고 합시다. 그리고 환율 $p_j$는 $L \le p_j \le U$를 만족하는 bound를 가지고 있다고 가정합시다..

문제의 출력은 $p_i$가 최대가 되는 i입니다.

 

그럼 이 문제를 reservation price policy 줄여서 RPP 알고리즘으로 분석을 해보도록 하겠습니다. 우선 파라미터 $\phi =  U/L$를 정의하겠습니다. 최대 환율과 최소 환율의 비율입니다. 알고리즘은 매우 단순합니다. $p_j \ge  p^* = \sqrt{UL}$를 만족하는 날에 모든 돈을 환전합니다. 물론 n번째날 까지 그런 날이 없다면 n번째 날 모든 돈을 바꿔야합니다. 이 알고리즘은 다음 3가지를 만족합니다. 

 

1. RPP 알고리즘의 competitive ratio는 $n$의 값을 아느냐 모르냐에 상관없이 $\sqrt{\phi}$를 만족합니다
2. $n$의 값을 알더라도 $\sqrt{\phi}$-competitive ratio보다 작을 수 없습니다.
3. $U$와 $L$을 모르고 $\phi$만 안다고 할 경우에 competitive ratio는 적어도 $\phi$를 보장합니다.

1번 Proof.

만약에 모든 n에 대하여 $p_j \le  p^*$라고 하면, RPP 알고리즘은 모든 돈을 마지막 날에 환전을 할 것이고 $p_n \ge L$을 보장합니다. 최적해는 $p_j \ge  p^* = \sqrt{UL}$이므로 ratio는 다음과 같습니다.

$$\frac{OPT}{ALG} \le \frac{\sqrt{UL}}{L} = \sqrt{\phi}$$

 

$p_j \ge  p^*$를 만족하는 j가 존재한다고 하면, RPP 알고리즘은 $p_j \ge \sqrt{UL}$를 만족하는 값을 보장합니다. 그리고 최적해는 $p_j \le  U$ 입니다. 둘 사이의 ratio는 다음과 같습니다.

$$\frac{OPT}{ALG} \le \frac{U}{\sqrt{UL}} = \sqrt{\phi}$$

 

2번 Proof.

1번 증명에서 밝혔듯이 n에 따라서 competitive ratio가 바뀌지는 않습니다.

 

3번 Proof.

우리가 $\phi$를 알고 있고 입력 시퀀스 $(p_1, p_2, ..., p_n)$에서 $p_i = 1, i\in [n-1]$을 RPP 알고리즘 ALG에 대입합시다. 이럴경우, $L\le U$이므로, $\phi \ge 1$을 만족해야 합니다.

만약 ALG가 day $i \in [n-1]$에 트레이드를 한다면, $p_n =\phi$라고 할 때, 최적해는 $p_n$에 트레이드하는 것입니다. 

 

$$\frac{OPT}{ALG} \le \frac{\phi}{1} = \phi$$

 

만약 ALG가 n번째 날에 $p_n = 1/\phi$에 환전을 한다고 하면, 최적해는 1이 되므로 $\phi$ ratio를 만족합니다.

 

$$\frac{OPT}{ALG} \le \frac{1}{1/\phi} = \phi$$

 

One-Way Trading

One-Way Trading은 TSS 알고리즘의 기본적인 접근방식입니다. 앞서 정리한 알고리즘에서는 특정한 환율에서 모든 돈을 바꿔야 했다면 이제는 분할해서 환전을 할 수 있다고 합시다. 물론 모든 돈을 n일이 되기전에 바꿔야합니다. 만약 n일 되었는데 환전을 안한 돈이 남아있다면, n일의 환율로 환전을 해야합니다. 

 

문제의 입력은 이전 문제와 같습니다. $(p_1, p_2, ..., p_n)$, $p_j$는 j번째 날 환율입니다. 그리고 환율 $p_j$는 $L \le p_j \le U$를 만족하는 bound를 가지고 있다고 가정합시다.

문제의 출력은 $f_1, f_2, ..., f_n \in [0,1]$ $f_i$는 i번째 날에 환전하는 전체 금액의 비율입니다. 즉, $\sum_{i=1}^{n}f_i = 1$를 만족해야합니다. 결과적으로, 총 환전하는 금액을 최대로 하는 비율의 시퀀스를 구하면 됩니다.

 

분할구매는 일괄구매보다 당연히 훨씬 강력합니다. 쉬운 알고리즘으로 competitive ratio를 $log \phi$로 구현할 수 있습니다. 알고리즘을 설명하도록 하겠습니다. 우선 보기쉽게 하기 위해서 $\phi = 2^k, k >0$로 가정합시다. 그렇다면 우리는 i번째 날의 환율을 $L2^i, i \in {0,1,...,k-1}$이라고 할 수 있습니다.

 

처음 $p_i$을 알았을 때, 알고리즘은 i에 현재까지 가장 큰 환율을 구합시다. 그리고 (i+1)/k 만큼의 비율을 환전합니다. 그리고 $i$를 $i^*$에 저장합니다. 이 알고리즘을 계속 반복합시다. 그리고 $i \le i^*$인 경우에는 그 날은 생략합니다. 아니면 $(i-i^*)/k$ 비율의 돈을 환전합니다. 이로써 $i^*$에는 가장 좋은 환율인 날을 기록합니다. 이것이 mixture of RPP 알고리즘입니다. 

 

Mixture of RPP 알고리즘은 $c(\phi)\log\phi, (c(\phi)\rightarrow 1, \phi \rightarrow \infty)$의 competitve ratio를 가지고 있습니다. 한번 증명해보도록 하겠습니다. 

 

입력 시퀀스 $(p_1, p_2, ..., p_n)$라고 합시다. 만약, $i_j$가 $L2^{i_j} \ge p_j$를 만족하는 가장 큰 인덱스라고 할 때,  $p_l = max(p)$를 만족하는 $l$이 있다고 할 때, $OPT = p_l \le L2^{i_l+1}$이라고 할 수 있습니다. 그렇다면 환율이 꾸준히 내려가는 형태가 아니면 우리는 $-1={i^*}_0<{i^*}_1<{i^*}_2<...<{i^*}_p=i_l$라고 할 수 있습니다. 그리고 알고리즘을 적용하면 다음과 같은 값이 나올 것입니다.

$$\sum_{j=1}^{p}\frac{{{i^*}_j - {i^*}_{j-1}}}{k}L2^{{i^*}_j} + \frac{k-i_l}{k}L$$

앞에는 $l$까지의 환전 값이고 뒤는 마지막날 남은 돈을 전부 환전한 값입니다. 앞에 값의 bound를 구해보자면, 값의 증가에서 skip이 없이 계속 시퀀스가 $-1,0,1,2,...,i_l$로 모든 환율을 구매하는 경우입니다. 이유는 당연히 계속 일정한 비율을 최고 환율이 아닌 환율에서 스킵없이 구매를 하기 때문입니다. 그리고 우리는 다음과 같은 $ALG$의 바운드를 구할 수 있습니다.

 

$$ALG \ge \frac{2^{i_l+1}-1}{k}L + \frac{k-i_l}{k}L$$

 

다음은 Randomized online 알고리즘에 대해서 정리해보도록 하겠습니다.