Approximation Algorithms

 

* 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다.

 

 

Approximation Algorithm이란 최적의 결과를 제공해주지는 않지만 최적에 가깝고 어느 정도의 결과를 보장해주는 알고리즘이다.

 

Load Balancing

m개의 machine과 n개의 job이 있다. 그리고 각 job은 $t_j$라는 processing time을 가지고 있다. 여러개의 job이 하나의 machine에 할당되었을 때, 다음으로 load를 정의한다.

$L_i = \sum{t_j}$

 

모든 machine에 대한 load의 최대 값을 makespan이라 한다.

makespan $L = max_i L_i$

 

Makespan을 최소화하는 문제를 Load balancing 문제이다.

 

 

List-scheduling algorithm

 

 

 

 

위 알고리즘은 그 때 step마다 제일 작은 load를 가지고 있는 machine에게 job을 할당하는 greedy algorithm이다. 이 알고리즘은 optimal 값을 보장해주진 않지만 2-approximation임을 보이자. 즉, optimal 값 $L^*$의 두 배보다 크지 않다.

 

 

Lemma

1. 어떠한 job j에 대해서도 $L^* \ge t_j$를 만족한다.

 

이는 당연하게도 job이 어느 한 machine에 할당되기 때문에 위의 식이 성립한다.

 

2. $L^* \ge {1 \over m} \sum {t_j} $

 

Job을 자를 수 있고 동등하게 나눠가지면 최소값인 평균값이 될 것인데, 그렇지 못하므로 어느 하나의 machine은 평균값을 초과하게 된다.

 

 

Theorem

Greedy algorithm is a 2-approximation

 

Pf )

어떠한 job j를 할당하는 상황을 가정하자. 이때, 가장 로드가 작은 machine i에 할당될 것이다. 할당되고 나서 load를 $L_i$라 하자. 그럼 할당되기 전의 상황은 모든 machine에서 가장 작은 로드를 가졌으므로 전체의 평균보다 작은 load를 가졌을 것이다.

$L_i - t_j \le {1 \over m} \sum {t_k}$

 

여기서 Lemma 2에 의해 아래의 식이 성립한다.

$L_i - t_j \le {1 \over m} \sum {t_k} \le L^*$

 

위의 식과 Lemma 1에 의해 최종적으로 아래가 성립한다.

$L_i = (L-i - t_j) + t_j \le L^* + L^* = 2L^*$

 

 

이 analysis가 tight한지 확인해보자. (실제로 이 수준까지 도달하는지)

 

 

 

 

위의 경우에서, 마지막에 processing time이 9인 job을 배치하면 2배에 가깝게 도달함을 볼 수 있다.

 

 

 

Improved Approximation Algorithm

위에서 볼 수 있듯이 마지막에 길이가 길면 비효율적으로 배치가 되므로, 크기가 큰 job부터 배치하는 알고리즘이다. (아래 참고)

 

 

 

 

Lemma

Job이 m보다 많을 때, $L^* \ge 2t_{m+1}$ 이 성립한다.

m+1 job을 어디엔가 배치해야하는데, 어디에 배치하더라도 $2t_{m+1}$보다 커지기 때문이다.

그리고, sort가 되어있으므로 $j \ge m+1$에 대하여,

 

$L^* \ge 2t_{m+1} \ge 2t_{m+1}$

이 성립한다.

 

 

Theorem

LPT rule is 3/2 approximation algorithm

 

Pf )

앞에서 했던 정리처럼, $t_j \le {1 \over 2}L^*$가 성립하므로,

$L_i = (L_i - t_j) + t_j \le L^* + {1 \over 2} L^* \le {3 \over 2}L^*$

 

 

위의 analysis는 tight하지 않다. 위의 알고리즘은 실제로 3/2 수준까지 도달하지 않는다는 뜻이다. LPT rule은 최종적으로 4/3-approximation으로 다른 방법을 통해 분석된다.

 

 

 

Center Selection

n개의 sites가 존재하고 center들은 반지름 r(C)를 가져 site들을 cover한다. 이때, 모든 sites들을 cover하면서 r(C)를 최소화하는 center들의 위치를 찾는 문제이다. (k는 고정)

 

 

 

 

 

Greedy algorithm

이 알고리즘에서는 center로써 site를 선택한다. 몇개의 center를 선택했을 때, 해당 center에서 가장 멀리에 있는 site를 center로 선택한다.

 

 

 

 

Observation

위의 알고리즘에서 형성된 center들은 적어도 r(C) 이상 떨어져있다. 위의 알고리즘에서 가장 멀리 있는 점을 선택했는데, r(C) 보다 center가 안에 있다면 그 점과의 거리가 새로운 r(C)가 될 것이다. 

 

 

Theorem

$C^*$는 optimal center 집합이라 하자. 그러면, $r(C) \le 2r(C^*)$ 이 성립한다. 

 

 

 

Pf )

위의 식이 성립하지 않는다 가정하자.

$r(C^*) \le {1 \over 2} r(C)$

 

위의 그림에서 처럼 center가 된 site들(C)에 대해 ${1 \over 2 r(C)}$ 의 반지름으로 원을 형성하자. 그러면 하나의 원안에는 $c_i^*$가 딱 1개만 존재한다.

 

하나의 원에 center가 없다고 하자. 그러면 그 원의 중심을 cover하는 $c^*$가 없으므로 모순이다.

반대로 한 원안에 두개이상의 center가 있다고 하자. 그러면 한 원안에는 $c^*$가 없을 것이고 \ $dist(c_i, c_j) \ge r(C)$이 성립하므로 그 원의 중심을 cover하지 못한다.

 

어떠한 site $s$를 생각하자. 그러면 C의 정의에 의해,

$dist(s, C) \le dist(s, c_i)$

 

주변의 $c_i^*$을 잡고 삼각 부등식에 의해,

$dist(s, C) \le dist(s, c_i) \le dist(s, c_i^*) + dist(c_i^*, c_i)$

 

마지막의 첫번째 항은 정의로 인해, 두번째 항은 위의 Observation에 의해 $r(C^*)$보다 작거나 같다.

$dist(s, C) \le dist(s, c_i) \le dist(s, c_i^*) + dist(c_i^*, c_i) \le r(C^*) + r(C^*) = 2r(C^*)$

 

따라서, $r(C) \le 2r(C^*)$ 이 성립한다.

 

이는 tight한 approximation이 아니며, 정확한 값은 발견되지 못했다.

 

 

 

Linear Programming Rounding - Vertex Cover

Weighted vertex cover

Vertex cover 문제를 만족하면서 cover를 구성하는 vertex weight의 합이 최소가 되도록하는 문제이다.

 

 

 

 

 

 

각 vertex를 0, 1로 할당가능한 변수 $x_i$라고 두면, 다음과 같은 최소화 문제로 바꿀 수 있다. 모든 edge를 cover해야하므로, $x_i + x_j \ge 1$로 둘 수 있다. 왜나하면 edge 양쪽 중에 하나는 무조건 선택되어야하기 때문이다.

 

 

 

 

이렇게 constraint가 존재하고, linear 식을 최소화/최대화하는 문제로 둘 수 있다. 그러면서 해당 변수가 integer만 가질 수 있으면, Integer Programming이라 한다. 

Integer programming 문제는 NP complete이다. (Vertext cover문제를 Integer programming으로 reduction 가능하기 때문)

 

 

 

 

LP는 poly-time에 실행가능하다. (선형대수에서 이를 푸는 방법에 대해 많이 연구되어 있다.)

 

 

따라서, Weighted vertex cover는 ILP문제이지만 LP문제로 approximation하여 풀자. LP로 minimize 문제를 풀면 $x_i$는 정수값이 아닌 실수값을 가지게 될 것이다. 이 때, 결과값 $x_i$를 반올림하여 정수로 만들어주고, 이때 1이 할당된 vertex를 모아 vertex cover를 만든다.

 

 

위의 방법으로 풀어도 vertex cover가 보장된다.

 

Pf )

$x_i^* + x_j^* \ge 1$ constraint는 그대로 존재하므로, 둘 중에 하나는 무조건 $1 \over 2$이상이 된다. 즉, 둘 중에 하나는 무조건 할당되고 이 edge는 cover된다.

 

 

이 알고리즘은 2-approxmation이다.

 

Pf )

$S^*$를 optimal vertex cover라 하고, $S$는 위의 알고리즘으로 얻어진 vertex cover이라고 하자.

LP로 얻어낸 값은 ILP로 얻어낸 값보다 작다. Constraint가 더 적어지기 때문에 더 작은 minimum값을 가질 수 있기 때문이다. 다른 방향에서 보면, LP를 그래프로 나타내면 가능한 부분이 area로 나타나고, ILP는 점으로 나타나지기 때문에 LP의 값이 더 작다.

 

$ \sum_{i \in S^*} {w_i} \ge \sum_{i \in S} {w_i x_i^*}$

 

 

반올림 기준이 $x_i^* \ge {1 \over 2}$이므로 다음이 성립한다.

 

$ \sum_{i \in S^*} {w_i} \ge \sum_{i \in S} {w_i x_i^*} \ge {1 \over 2} \sum_{i \in S} {w_i}$ 

 

$2 \sum_{i \in S^*} {w_i} \ge \sum_{i \in S} {w_i}$

 

따라서, 2-approximation이다.