Analysis on the online search problem using prediction probability

본 논문은 직선 위에서 탐색자(searcher)가 위치가 알려지지 않은 목표물(target)을 찾아야 하는 문제를 다룬다. 이는 온라인 알고리즘 분야에서 잘 알려진 문제이고, 탐색자의 이동을 결정하는 알고리즘의 성능은 경쟁 분석(competitive analysis)으로 평가한다. 이 분석에서는 알고리즘에 의한 탐색자의 총 이동 거리와 탐색자의 초기 위치에서 목표물 위치까지의 거리를 비교한다. 여기서, 후자는 탐색자가 목표물의 위치를 미리 알고 있다면 최단으로 이동할 수 있는 거리이다. 본 논문에서는 탐색 알고리즘이 데이터를 학습한 머신 러닝 알고리즘의 도움을 받을 수 있는 상황을 가정한다. 탐색자는 머신 러닝 알고리즘의 예측을 활용할 수 있고, 이러한 경우 탐색 알고리즘의 성능이 향상될 수 있음을 보인다. 특별히 머신 러닝의 예측이 맞을 확률이 주어질 때, 알고리즘의 성능을 분석한다.