스키 대여 문제: 최적 비용을 위한 랜덤화 알고리즘

이 글에서는 온라인 알고리즘에서 흥미로운 예시인 고전적인 스키 대여 문제를 다룹니다. 문제: 스키어는 스키를 탈 날짜를 모릅니다. 대여는 하루에 1단위의 비용이 들고, 구매는 B단위의 비용이 듭니다. 이 글에서는 최적의 오프라인 솔루션을 자세히 설명하고, 그런 다음 경쟁 비율이 2인 간단한 온라인 알고리즘을 분석합니다. 중요한 것은 이산 문제를 근사하기 위해 연속 확률 분포를 사용하는 랜덤화 알고리즘을 심층적으로 파고들어, 간단한 접근 방식보다 훨씬 우수한 약 e/(e-1)의 기대 경쟁 비율을 달성하는 점입니다. 단일 의사 결정에서는 현실 세계에 직접 적용할 수 없지만, 이 알고리즘은 많은 유사한 선택을 포함하는 시나리오에 대해 이론적으로 최적의 전략을 제공합니다.