이번에 살펴볼 문제는 간단하지만 흥미로운 문제입니다. 우리에게 어떤 방향이 없는 그래프 \(G = (V, E)\)가 주어졌습니다. 이제 이 그래프의 어떤 간선 \((u, v) \in E\)를 \( \langle u, v \rangle \)이나 \( \langle v, u \rangle \)와 같이 방향을 주도록 합시다. 방향을 주는 방법은 여러 가지가 있겠지만, 그중에서 우리는 각 정점마다 들어오는 간선의 개수를 최소화 시키는 것을 구해보고자 합니다. 좀더 엄밀히 말하자면, \(G = (V, E)\)가 주어졌을 때, 우리의 목표는
- 각 간선 \( (u,v) \in E \)에 대해, \( \langle u, v \rangle \in A \)이거나 \( \langle v, u \rangle \in A \)를 만족하면서,
- 어떤 정점으로 들어오는 간선의 개수(즉, in-degree)의 최댓값을 최소화시키는
방향이 있는 그래프 \(D = (V, A)\)를 찾는 것입니다. 두 번째 항목은 모든 정점의 in-degree가 그 값보다 작거나 같은 것과 동일합니다.
만약 처음부터 \(G\)의 모든 정보를 알고 있다면, 이 문제는 쉽습니다. 특히, \(G\)에 순환(cycle)이 없다면, 즉 \(G\)가 forest라면, 모든 정점의 in-degree를 최대 1로 만드는 orientation을 쉽게 구할 수 있습니다. 방법은 간단합니다. 임의의 forest의 connected component는 모두 tree이므로, 임의의 tree에 대해서 모든 정점의 in-degree가 최대 1이 되는 orientation을 구하면 충분합니다. 어떤 tree에서 정점을 하나 임의로 잡고 이를 root로 둡니다. 그러고 난 후, 모든 간선들을 root에서 나가는 쪽으로 방향을 주는 것입니다. 그러면 root를 제외한 모든 정점의 in-degree가 1이 되고 root는 0의 in-degree를 갖는다는 것을 확인할 수 있습니다.
참고로 일반적인 \(G\)에 대해서도 in-degree의 최댓값을 최소화시키는 orientation을 다항 시간에 구할 수 있습니다. 이 글에서 따로 다루지는 않겠지만, 그렇게 어렵지 않으므로 직접 생각해 보시기 바랍니다. 이 글에서는 순환이 없는 \(G\)에 대해서만 다룰 예정입니다.
자, 이제 문제를 좀더 어렵게 바꾸도록 해보죠. 만약 우리가 \(G\)의 모든 정보를 아는 게 아니라면 어떻게 될까요? 좀더 상황을 정확히 설명하자면, 처음에는 정점 \(V\)의 정보(\(n := |V|\))만 주어지고, 매 시간마다 \(E\)의 간선이 하나씩 들어오는 것입니다. 게다가 매번 간선이 들어오면 우리는 반드시 그 간선의 방향을 정해주어야 합니다. 흔한 온라인 문제(online problem)의 세팅이죠.
이제부터 이 문제를 세 가지의 다양한 버전으로 생각해 보고자 합니다. 첫 번째는 대개의 온라인 문제가 그러하듯이 이전에 들어온 간선의 방향을 한번 정하면 다시는 바꿀 수 없는 경우입니다. 이때는 불가피하게 어떤 정점의 in-degree가 1보다 커지는 상황이 발생할 수 있습니다. 과연 그 값이 얼마큼 커지게 될까요? 안타깝게도 이 문제를 해결하는 어떤 deterministic algorithm도 임의의 입력에 대해 모든 정점의 in-degree를 \( \log_2 n \)보다 작아지도록 만들 수는 없습니다.
따라서 두 번째 버전에서는 이전에 이미 정해진 간선의 방향을 바꿀 수 있는 자유를 알고리즘에게 주고자 합니다. 그러면 분명히 매번 모든 정점의 in-degree를 1 이하로 유지할 수 있습니다. 하지만 예전에 자신이 했던 선택을 번복하는 것은 그렇게 보기 좋은 모습은 아니죠? 따라서 이 버전의 목표는 번복의 총 횟수를 최소화시키는 것입니다. 과연 몇 번의 번복으로 매번 최적의 orientation을 유지할 수 있을까요? 안타깝게도 우리는 어떤 deterministic algorithm이 주어지더라도 그 알고리즘이 \( \Omega ( n \log n) \)의 번복을 해야만 매번 모든 정점의 in-degree를 1 이하로 유지할 수 있도록 만들 수 있습니다.
두 번째 버전의 문제는 매번 최적의 orientation을 유지하는 데에 있습니다. 알고리즘에게 약간의 자유를 더 준다면 어떻게 될까요? 즉, 이번에는 매번 모든 정점의 in-degree를 1이 아닌 2 이하로 유지하는 것입니다. 그러면 놀랍게도 총 \( O(n) \)의 번복만으로 이를 충분히 유지할 수 있다는 것을 보일 수 있습니다. 아래에서 이 세 가지에 대해서 차근히 알아보도록 하겠습니다.
이전에 정한 간선의 방향을 바꿀 수 없는 경우
첫 번째 버전이 무엇이었는지 다시 말씀드리겠습니다. 매번 간선이 들어올 때마다 이 간선의 방향을 반드시 정해주어야 합니다. 이와 더불어 이전에 정한 간선의 방향을 이후에는 절대로 번복할 수 없다는 조건도 있죠. 이러한 경우에는 안타깝게도 임의의 deterministic algorithm이 \( \log_2 n \) 보다 잘할 수 없다는 것을 보일 수 있습니다. 먼저 deterministic algorithm을 상대할 것이므로 우리는 이 알고리즘을 망치려 드는 적응형 상대방(adaptive adversary)을 고안하면 증명이 끝납니다.
다음과 같은 상대방을 생각해 봅시다. 처음에는 알고리즘에게 정점이 \(n = 2^k\)개 있다고 알려줍니다. 이 상대방은 총 \(k\) 번의 단계를 거쳐 간선을 보여줄 것입니다.
첫 번째 단계에서는 정점들을 두 개씩 짝지어 간선을 보여줍니다. 간선을 보여주는 순서는 그다지 상관 없습니다.
그러고는 알고리즘이 어떻게 간선의 방향을 정했는지를 살펴봅니다.
그러면 첫 번째 단계가 끝난 후에는 총 \( \frac{n}{2} = 2^{k - 1}\) 개의 정점이 in-degree가 1인 상황이 됩니다. 두 번째 단계에서는 이 정점들만 가지고 다시 두 개씩 짝을 지어 간선을 보여줍니다.
이번 단계가 모두 끝난 후에는 분명 총 \( \frac{n}{4} = 2^{k - 2} \) 개의 정점이 in-degree가 2인 상황이 될 것입니다. 그 정점들을 모아서 또 세 번째 단계를 돌리면 다음 그림과 같은 모양이 됩니다.
이렇게 이전 단계에서 높은 in-degree를 갖는 정점만 모아서 짝을 지어 간선을 보여주면 알고리즘의 입장에서는 이전에 정한 간선의 방향을 번복할 수 없어서 울며 겨자 먹기로 in-degree를 높힐 수 밖에 없습니다. 자세히 말해, 매 \(t\) 번째 단계가 끝난 후에는 정확히 \(t\)의 in-degree를 갖는 정점의 개수가 \( \frac{n}{2^t} = 2^{k - t} \)개 존재하게 됩니다. 따라서 이 상대방을 상대해서는 어떤 알고리즘이라도 \(k\) 번째 단계가 끝난 후에는 in-degree가 \(k = \log_2 n\)인 정점이 반드시 생길 수 밖에 없게 됩니다.
이전의 결정을 번복하면서 매번 최적해를 유지하는 경우
위 절의 결과를 통해서 보다 좋은 해를 유지하기 위해서는 이전에 정한 방향을 뒤바꾸어 줄 필요가 있다는 것을 알 수 있습니다. 하지만, 이전의 결정을 번복하는 행위는 온라인 환경에서는 극도로 기피되는 것이죠. 그렇지 않고 원하는 대로 막 바꿀 수 있다면, 그냥 입력을 모두 받은 후에 그제야 알고리즘을 수행하면 그만이니 말입니다. 따라서 우리의 목표는 최소한의 번복을 통해 좋은 해를 유지하는 것입니다.
먼저 매번 최적의 orientation을 유지한다면 몇 번의 번복이 필요할까요? 이 경우에는 \( \Omega (n \log n) \)의 번복이 필요합니다. 이를 증명하기 위해서 요긴하게 쓰일 정리를 소개하겠습니다.
정리 1. 알고리즘이 번복을 많이 하도록 만드는 방법
이전에 정한 간선의 방향을 번복하면서 매번 모든 정점의 in-degree를 1 이하로 유지하는 알고리즘을 가정하자. 이 알고리즘이 어떤 순간 기저 그래프(underlying graph)가 각각 길이가 \(\ell\)인 경로 그래프(path graph)인 방향 그래프 \(D_1\), \(D_2\)를 유지하고 있다고 하자. 이 알고리즘에 간선 하나를 보여주어 이 알고리즘이 최소 \( \left\lceil \frac{\ell}{2} \right\rceil \)의 번복을 한 후 길이가 \( 2\ell + 1 \)인 경로 그래프를 기저 그래프로 갖는 방향 그래프 하나를 유지하도록 만들 수 있다.
[증명] 먼저 어떤 경로 그래프에서 모든 정점이 1 이하의 in-degree를 갖는 orientation에는 반드시 in-degree가 0인 정점이 정확히 하나 존재하고, in-degree가 1인 leaf가 적어도 하나 존재하게 됩니다. \(D_1\)에서 in-degree가 0인 점을 \(x\), in-degree가 1인 leaf를 \(u\)라고 하겠습니다. 만약 in-degree가 1인 leaf가 두 개 존재하면 그중 \(x\)에서 거리가 더 먼 것을 \(u\)로 정하겠습니다. 두 거리가 같으면 아무거나 정하면 됩니다. \(D_2\)에 같은 작업을 적용하여 얻은 정점을 각각 \(y\)와 \(v\)라고 하겠습니다.
그러면 \(x\)에서 \(u\) 사이의 거리(그리고 \(y\)에서 \(v\) 사이의 거리)는 분명 \( \left\lceil \frac{\ell}{2} \right\rceil \)보다 길거나 같을 것입니다. 이제 이 알고리즘에게 간선 \((u, v)\)를 보여줍시다. 우리가 고려하는 알고리즘은 매번 반드시 모든 정점의 in-degree를 2를 넘지 않도록 유지해야 합니다. 따라서, 최소한 \( x \)에서 \( u\)의 거리 혹은 \( y \)에서 \(v\)의 거리 중 더 짧은 것 만큼의 번복은 필수적입니다. 그것보다 적게 번복해서는 원하는 바를 이룰 수 없기 때문이죠.
따라서 이 알고리즘은 최소한 \( \left\lceil \frac{\ell}{2} \right\rceil \)의 번복을 해야합니다. 또한 두 경로 그래프의 끝점을 잇는 간선을 보여주었으므로 합쳐진 그래프도 경로 그래프가 됩니다. ■
이 정리를 활용하여 다음과 같은 적응형 상대방을 만들 수 있습니다. 먼저 처음에 \( n = 2^k \) 개의 정점을 알고리즘에게 알려줍니다. 이제 위 절에서 본 상대방과 비슷하게 총 \(k\) 번의 단계를 거칩니다. 첫 번째 단계는 정점들을 두 개씩 짝지어 간선을 보여줍니다. 그러면 두 번째 단계에서는 길이가 1인 경로 그래프를 기저 그래프로 갖는 방향 그래프가 총 \( \frac{n}{2} \)개 존재합니다. 이를 두 개씩 묶어 정리 1에서의 작업을 진행합니다. 한 쌍을 처리할 때 최소한 \( \lceil \frac{1}{2} \rceil = 1 \)의 번복이 필요하고 총 \( \frac{n}{4}\) 쌍이 존재하므로 두 번째 단계에서는 최소한 \( \frac{n}{4} \)의 번복을 수행해야 합니다.
세 번째 단계가 어떻게 진행되는지까지 살펴보죠. 두 번째 단계가 끝나면 알고리즘은 총 \( \frac{n}{4} \) 개의 길이가 3인 경로 그래프를 기저 그래프로 갖는 방향그래프를 갖게 됩니다. 똑같이 두 개씩 묶어 정리 1을 적용하면 각 쌍마다 최소 \( \lceil \frac{3}{2} \rceil = 2 \)의 번복을 해야하므로 이 단계에서만 총 \( 2 \times \frac{n}{8} = \frac{n}{4} \) 번의 번복을 필요로 합니다.
따라서, 매 \(t\) 번째 단계(단, \(t \geq 2\))가 시작할 때 길이가 \( 2^{t - 1} - 1 \)인 경로 그래프를 기저 그래프로 하는 방향 그래프가 총 \( \frac{n}{2^{t -1}} \)개 존재하고 정리 1의 작업을 통해 이 단계에서만 총 \[ \left\lceil \frac{2^{t - 1} - 1}{2} \right\rceil \times \frac{n}{2^t} = 2^{t - 2} \times \frac{n}{2^t} = \frac{n}{4} \] 번의 번복을 필요로 합니다. 총 \(k\) 단계로 이루어져 있으므로 번복의 총 횟수는 최소한 \[ (k - 1) \times \frac{n}{4} = ( \log_2 n - 1) \times \frac{n}{4} = \Omega(n \log n) \]이 된다는 것을 알 수 있습니다.
이전의 결정을 번복하면서 매번 근사해를 유지하는 경우
지금까지 이전의 결정을 번복할 수 없는 경우 어떤 deterministic algorithm이 아무리 잘해도 \( \log_2 n \)의 in-degree는 가질 수 밖에 없다는 것과 이전의 결정을 번복할 수 있을 때 매번 최적해를 유지하려면 아무리 적어도 총 \( \Omega(n \log n) \)의 번복이 필요하다는 것을 알아보았습니다. 마지막으로 그 중간 지점은 어떻게 될지를 알아보도록 하죠. 바로 번복이 가능하면서 동시에 매번 모든 정점의 in-degree가 2를 넘지 않도록 유지하는 것입니다. 그러면 놀랍게도 총 번복의 횟수를 \( O(n) \)으로 하면서 매번 모든 정점의 in-degree를 원하는 수준으로 유지할 수 있습니다. 먼저 알고리즘이 무엇인지 살펴보도록 하겠습니다.
알고리즘 1. Approximate in-degree balancing with reassignments
초기 입력: 정점 \(V\) (단, \(n := |V|\))
출력: 모든 정점의 in-degree가 2 이하인 orientation
- 매번 간선 \((u, v)\)가 들어오면 다음을 수행한다.
- 현재 \(u\)가 속한 tree에서 in-degree가 1 이하인 정점 중 \(u\)까지의 거리가 가장 짧은 정점을 \(u^\prime\)이라고 하고 \(u^\prime\)에서 \(u\)까지의 방향이 있는 경로를 \(P_u\)라고 하자.
- 현재 \(v\)가 속한 tree에서 in-degree가 1 이하인 정점 중 \(v\)까지의 거리가 가장 짧은 정점을 \(v^\prime\)이라고 하고 \(v^\prime\)에서 \(v\)까지의 방향이 있는 경로를 \(P_v\)라고 하자.
- 만약 \( |P_u| \leq |P_v| \)이면, \( P_u \)위의 모든 간선의 방향을 뒤집고 \( (u, v) \)의 방향을 \( \langle v, u \rangle \)로 한다.
- 그렇지 않으면, \( P_v \)위의 모든 간선의 방향을 뒤집고 \( (u, v) \)의 방향을 \( \langle u, v \rangle \)로 한다.
이 알고리즘이 동작하는 방식은 간단합니다. 매번 간선 \( (u, v) \)가 들어오면 각 정점이 속한 tree에서 in-degree가 1 이하인 정점 중 각 정점에서 가장 가까운 정점 \(u^\prime\, v^\prime \)을 찾습니다. 만약 \(u\)나 \(v\)의 in-degree가 시작부터 1 이하였으면 자기 자신이 선택될 수도 있습니다. 두 경로 \(P_u = u^\prime \rightarrow u \)와 \(P_v = v^\prime \rightarrow v \)에 대해서 더 짧은 쪽을 취한 후, 해당 경로의 방향을 모두 뒤집는 작업을 합니다.
일단 알고리즘이 정확히 동작한다는 것은 쉽게 보일 수 있습니다. 먼저, 단계 1-i과 1-ii에서 \(u^\prime\)과 \(v^\prime\)이 존재한다는 것은 자명합니다. 그렇지 않다면 분명히 원래 그래프에 순환이 존재할 수 밖에 없기 때문이죠. 만약 알고리즘이 \(P_u\)를 취했다면, \( u^\prime \)의 in-degree만 정확히 1이 증가하게 됩니다. 처음에 \( u^\prime \)의 in-degree는 1보다 작거나 같은 것으로 골랐으므로 알고리즘은 정확히 동작하게 됩니다. 반대로 \(P_v\)를 고른 경우에도 동일한 방식으로 증명할 수 있습니다.
따라서 문제는 번복을 몇 번 하는가입니다. 먼저 이 알고리즘이 총 \( O(n \log n) \)의 번복을 수행한다는 것을 보이도록 하겠습니다. 좀더 자세히는 매번 간선이 들어올 때마다 최대 \( O(\log n) \) 번의 번복을 수행한다는 것을 보일 것입니다. 그러면 간선의 개수가 \(n\)을 넘지 않을 것이므로 자연스럽게 처음에 보이고자 하는 것을 증명할 수 있습니다.
정리 2. 알고리즘 1이 매번 번복하는 횟수
알고리즘 1의 단계 1-i에서 \(u\)가 속한 방향이 있는 tree를 \(T_u\)라고 하자. 그러면 \[ |P_u| \leq \log_2 |V(T_u)| \leq \log_2 n \]을 만족한다. 비슷하게 단계 1-ii에서 \(v\)가 속한 방향이 있는 tree를 \(T_v\)라고 하였을 때, \[ |P_v| \leq \log_2 |V(T_v)| \leq \log_2 n \]도 만족한다.
[증명] 어차피 동일한 방식으로 증명하면 되므로 \(T_u\)에 대해서만 보이도록 하겠습니다. 먼저 간단히 표기하기 위해서 \( h := |P_u| \)라고 하겠습니다. 그리고 아래 그림과 같이 \(T_u\)에서 \(u\)를 root로 하고 \(u\)로 향하는 간선만으로 이루어진 방향이 있는 tree를 고려하겠습니다.
그러면 그 tree는 \(u\)를 기준으로 거리가 \( h-1 \)인 정점은 모조리 in-degree가 2가 됩니다. 따라서 우리는 \( h \geq 0\)에 대해 \[|V(T_u)| \geq 2^{h + 1} - 1 \geq 2^h \]임을 이끌어낼 수 있고, 이를 정리하면 정리의 식을 얻을 수 있습니다. ■
우리는 번복의 총 횟수에 대해 좀더 엄밀한 분석을 할 수 있습니다. 임의의 \(m\)에 대해서 이 알고리즘이 \(m\)개의 간선을 입력 받을 동안 번복한 최대 횟수를 \(R(m)\)이라고 하겠습니다. 먼저 \(m \leq 1\)인 경우에는 번복할 것이 없으므로 \(R(0) = R(1) = 0\)이 됩니다.
그러면 \(m > 1\)인 경우에는 어떻게 될까요? 마지막 \(m\) 번째 간선 \( (u, v) \)를 넣기 전에 알고리즘은 어떤 방식으로든 \(T_u\)와 \(T_v\)를 만들었을 것입니다. 그때 \(T_u\)의 정점의 개수를 \(k\)라고 한다면 분명히 \(T_v\)의 정점의 개수는 \( m - k + 1 \)을 넘지 않을 것입니다. 왜냐하면 그동안 \(m - 1\) 개의 간선을 입력 받았고 \(T_u\)가 그중 \(k - 1\) 개의 간선으로 이루어졌기 때문입니다. 여기서 이 알고리즘이 동작하면 최대 \[ \log_2 \min \{ k, m - k + 1 \} \] 의 번복을 수행할 것입니다. 따라서 우리는 \( m > 1 \)에 대해 다음과 같은 점화식을 이끌어낼 수 있습니다.
\[ R(m) \leq \max_{1 \leq k \leq m } [ R(k - 1) + R(m - k) + \log_2 \min\{ k, m - k + 1 \} ] \]
그리고 놀랍게도 이 점화식은 \(R(m) = O(m)\)을 만족하게 됩니다.
정리 3. 알고리즘 1이 총 번복하는 횟수
\(R(m) \leq 2m - \log_2 (m + 1) \)이다.
[증명] 귀납법을 통해 보이도록 하죠. \(m = 0, 1\)인 경우는 자명하므로 \(m \geq 2\)인 경우에 대해서 생각해 보도록 합시다. 만약 우리가 임의의 \(1 \leq k \leq m \)에 대해서 \[ R(k - 1) + R(m - k) + \log_2 \min\{ k, m - k + 1 \} \leq 2m - \log_2 (m + 1) \]임을 보일 수 있으면 점화식도 곧장 성립하게 됩니다. 일반성을 잃지 않고 \(k \leq m - k + 1\)이라고 하겠습니다.(반대의 경우는 \(k^\prime := m - k +1\)로 두면 됩니다.) 그러면 induction hypothesis에 의하여 \[ \begin{array}{ll}R(k - 1) + R(m - k) + \log_2 \min\{ k, m - k + 1 \} & \leq 2(k - 1) - \log_2 k + 2(m - k) - \log_2 (m-k + 1) + \log_2 k \\ &= 2m - \log_2 (m - k + 1) - 2 \end{array} \]라는 사실을 이끌어낼 수 있습니다.
가정에서 \( k \leq m - k + 1 \)이라고 하였으므로, \( k \leq \frac{m + 1}{2} \)를 알 수 있으며, 이를 통해 \[ \log_2 (m + 1) - \log_2 (m - k + 1) = \log_2 \frac{m + 1}{m - k + 1} \leq \log_2 2 = 1 \]이라는 사실을 얻을 수 있습니다. 이를 위 식에 적용하면 \[ 2m - \log_2 (m - k + 1) - 2 = 2m - \log_2 (m + 1) + \log_2 \frac{m + 1}{m - k + 1} - 2 \leq 2m - \log_2 (m + 1) - 1 \]이 되어 정리를 증명할 수 있게 됩니다. ■
마치며
이 글에서는 비순환 그래프에서 매번 간선이 들어올 때마다 모든 정점의 in-degree가 1(또는 2) 이하가 되도록 방향을 정하는 온라인 문제를 생각해 보았습니다. 다양한 버전의 문제를 고민하였는데, 정리하면 다음과 같습니다.
- 만약 알고리즘이 이전에 들어온 간선의 방향을 번복할 수 없으면 임의의 deterministic algorithm에게는 아무리 잘해도 모든 정점을 \( \log_2 n \)보다 적은 in-degree로 유지할 수 없는 입력이 존재합니다.
- 이전의 결정을 번복할 수 있을 때, 알고리즘이 매번 최적해를 유지해야 한다면 임의의 deterministic algorithm에게는 아무리 잘해도 총 \( \Omega(n \log n) \)의 번복이 필수적인 입력이 존재합니다.
- 최적해 대신 모든 정점의 in-degree를 2 이하로 유지한다면 총 \( O(n) \)의 번복으로 이를 유지하는 deterministic algorithm이 존재합니다.
입력이 만약 비순환 그래프가 아니라 임의의 아무 그래프면 어떻게 될까요? 일단, 처음 두 항목은 그대로 유지됩니다. 비순환 그래프에서도 안 되는데 임의의 그래프에서라고 잘 할 수는 없을 테니 말이죠. 그렇다면 마지막도 유지가 될까요? 놀랍게도 거의 비슷한 알고리즘으로 비슷한 결과를 얻을 수 있습니다. 좀더 자세히 말씀드리면, 어떤 그래프가 주어졌을 때, 모든 정점에 대해 in-degree가 \( \Delta \) 이하인 orientation이 존재할 \( \Delta\) 중 최솟값을 \( \Delta^\star \)라고 했을 때, 이번에 소개한 알고리즘을 약간만 수정하면 기존의 결정을 \(O(n)\) 번 번복하여 매번 모든 정점의 in-degree를 최대 \( 8\Delta^\star \)로 유지하는 알고리즘을 만들 수 있습니다. 다음 시간에는 이를 함께 살펴 보도록 하지요.
혹시 잘못된 점을 발견하셨거나 궁금하신 점이 있으시면 언제든지 댓글로 알려주세요. 고맙습니다.
참조 문헌
[1] Anupam Gupta, Amit Kumar, and Cliff Stein. Maintaining assignments online: Matching, scheduling, and flows. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pp. 468-479. SIAM, 2014.