arXiv:2605.07080cs.AIcs.DS2026-05

解决未知总量资源的在线分配问题,提升稀缺物资分配效率。

Online Allocation with Unknown Shared Supply

论文配图:Online Allocation with Unknown Shared Supply
图 1 · 摘自论文原文
  • 设计阈值比例策略GPA,动态分配有限资源
  • 理论证明性能接近最优,误差项与总供应量无关
  • 可融合专家或模型预测,对错误建议仍保持稳健

许多现实资源分配系统(如人道主义物流、疫苗分发)需在需求明确前预置有限供给至多个地点,缺货将导致不可逆的服务损失。本文提出在线共享供给分配(OSSA)问题,一种状态相关在线模型:中心枢纽在固定运输成本和缺货惩罚下,向多个面临序列需求的站点分配有限且未知总量的供给,无法补货且不允许延迟交付。针对此问题,我们提出确定性阈值比例策略GPA,证明其性能逼近离线最优解,近似比为4/3,附加误差项与总供给无关。同时给出紧致下界,表明4/3比值不可改进,且该误差依赖性在随机算法中亦不可避免,即使已知总供给。最后,我们构建学习增强型扩展版本,有效整合不完美预测(如人工或机器学习模型),在高质量建议下表现优异,同时对任意劣质建议具备鲁棒性。合成与真实数据实验表明,当总供给稀缺时,GPA显著优于自然基线。

原文摘要 · Abstract (English)

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.

在线优化资源分配鲁棒性学习增强

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。