알 수 없는 공유 공급 하에서의 온라인 할당

Online Allocation with Unknown Shared Supply

많은 실제 자원 할당 시스템, 예를 들어 인도적 지원 물류 및 백신 배포는 수요가 발생하기 전에 제한된 공급을 여러 위치에 미리 배치해야 하며, 재고 부족은 되돌릴 수 없는 서비스 손실을 초래합니다. 이를 연구하기 위해, 우리는 온라인 공유 공급 할당(OSSA) 문제를 제안합니다. OSSA는 중앙 허브가 고정 운송 비용과 판매 손실 페널티 하에서 순차적인 수요에 직면한 여러 위치에 유한하고 알려지지 않은 공급을 할당하는 상태 기반 온라인 모델입니다. 고전적인 주문 생산 또는 맞춤 생산 재고 모델과 달리, OSSA는 재고 보관을 허용하지 않으며, 보충은 향후 수요에 대한 대비일 뿐입니다. OSSA 문제를 해결하기 위해, 우리는 결정론적 임계값-비례 정책인 GPA를 제안하고, GPA가 총 공급과 독립적인 더항을 고려하면 오프라인 최적해에 $4/3$의 근사 성능을 달성한다는 것을 증명합니다. 이를 뒷받침하기 위해, GPA의 $4/3$ 비율이 최적이며, 총 공급을 미리 알고 있는 확률적 알고리즘이라도 더항 오차가 불가피하다는 것을 보여주는 하한 경계를 제시합니다. 마지막으로, GPA의 학습 기반 확장을 개발하여, 실제 환경에서 흔히 사용되는 불확실한 예측(예: 인간 전문가 또는 머신러닝 모델에서 제공하는 예측)을 통합합니다. 이를 통해 고품질의 조언을 활용하면서도, 임의의 부정확한 예측에 대한 강건성을 확보합니다. 합성 데이터 및 실제 데이터를 사용한 실험 결과, GPA는 전반적인 공급이 부족한 경우 기존 방식보다 우수한 성능을 보였습니다.

Many real-world resource allocation systems, such as humanitarian logistics and vaccine distribution, must preposition limited supply across multiple locations before demand is realized while stockouts incur irreversible service losses. To study this, we introduce the Online Shared Supply Allocation (OSSA) problem, a stateful online model in which a central hub allocates a finite, unknown supply to multiple sites facing sequential demand under fixed-charge transportation costs and lost-sales penalties. Unlike classical make-to-stock or make-to-order inventory models, OSSA precludes backlogging and replenishment only hedges against future demand. To tackle OSSA, we propose a deterministic threshold-proportional policy GPA and prove that it achieves a $4/3$-approximation to the offline optimum up to an additive term independent of the total supply. We complement this with matching lower bounds showing that the $4/3$ ratio is tight and that the additive-error dependence is unavoidable, even for randomized algorithms that know the total supply upfront. Finally, we develop a learning-augmented extension to GPA that principally incorporates imperfect forecasts (e.g., from human experts or ML models) commonly available in practice, enabling us to exploit high-quality advice while being robust against arbitrary bad ones. Synthetic and real-world experiments show that GPA outperforms natural baselines with global supply is scarce.