자원 할당 문제를 위한 거의 최적 온라인 알고리즘 및 빠른 근사 알고리즘

우리는 확률적 입력을 가진 온라인 환경과 오프라인 환경 모두에서 자원 할당 문제의 클래스에 대한 알고리즘을 제시합니다. 이 문제 클래스에는 Adwords 문제와 같은 여러 흥미로운 특수 경우가 포함됩니다. 온라인 설정에서 우리는 시간에 따라 변할 수 있는 알려지지 않은 분포를 가진 i.i.d 모델의 일반화인 적대적 확률적 입력 모델이라는 새로운 분포 모델을 도입합니다. 이 모델에서 우리는 자원 할당 문제에 대해 최대 약한 가정으로 1-O(ε) 근사 알고리즘을 제공합니다: 단일 요청이 소비할 수 있는 최대 자원의 비율과 자원의 총 용량 비율, 및 단일 요청이 기여하는 이익 비율과 최적 이익 비율이 (ε2/log(1/ε)2)/(log n + log (1/ε)) 이하일 때, 여기서 n은 사용 가능한 자원의 수입니다. 이 비율이 #949;2/log n인 경우가 있어, i.i.d 모델에서도 1-o(ε)의 경쟁 비율을 가질 수 있는 랜덤화된 알고리즘은 존재하지 않습니다. 우리가 요구하는 비율의 상한은 i.i.d 경우에 대한 이전의 상한을 n 배 개선합니다.