온라인 확률적 매칭: 오프라인 통계를 기반으로 한 온라인 행동

우리는 Feldman et al.이 제안한 온라인 확률적 매칭 문제를 고려합니다. Feldman J, Mehta A, Mirrokni VS, Muthukrishnan S (2009) 온라인 확률적 매칭: 1 - 1/e를 이기기. 연례 IEEE 심포지움. 컴퓨터 과학의 기초. 117–126을 디스플레이 광고 할당 모델로 사용합니다. 우리는 이분 그래프를 주어집니다; 그래프의 한 쪽은 고정된 빈 집합에 해당하고, 다른 쪽은 가능한 공의 유형 집합을 나타냅니다. 각 시간 단계마다, 공은 주어진 분포에서 독립적으로 샘플링되며 빈 집에 도착할 때 매칭되어야 합니다. 목표는 할당의 수를 최대화하는 것입니다. 우리는 이 문제에 대해 0.702의 경쟁 비율을 가진 온라인 알고리즘을 제시합니다. 우리의 결과 이전에, 각 유형의 도착 공의 수가 정수라는 가정 하에 1 - 1/e보다 나은 경쟁 비율을 가진 알고리즘이 알려져 있었습니다. 알고리즘의 주요 아이디어는 몬테카를로 샘플링을 사용하여 최적 오프라인 솔루션의 결정에 대한 통계를 수집하고 이러한 통계를 사용하여 온라인 알고리즘의 결정을 안내하는 것입니다. 우리는 또한 비율이 정수일 때 우리의 알고리즘이 0.705의 경쟁 비율을 달성한다는 것을 보여줍니다. 어려운 측면에서, 우리는 알려진 분포 모델 아래에서 (그리고 그 이후에는 순열 모델 아래에서) 어떤 온라인 알고리즘도 0.823보다 나은 경쟁 비율을 가질 수 없음을 증명합니다. 이는 Goel과 Mehta가 증명한 5/6의 어려움 결과를 개선합니다. Goel G, Mehta A (2008) 온라인 예산 매칭을 무작위 입력 모델에서 광고어드워드에 적용한 논문. ACM-SIAM 심포지움 이산 알고리즘 982–991.