未知共享库存的在线分配

arXiv cs.AI 论文
online-allocation optimization resource-management learning-augmented-algorithms approximation-theory arxiv

摘要

本文提出了在线共享库存分配问题，并设计了一种确定性的阈值比例策略（GPA），该策略能达到离线最优解的 4/3 近似比。文章还介绍了一种学习增强型扩展方法，以处理不完美的预测，并在合成数据及真实世界实验中展示了其优越的性能。

arXiv:2605.07080v1 公告类型：新论文 摘要：许多现实世界的资源分配系统（如人道主义后勤和疫苗分发）必须在需求实现之前，将有限的库存预先部署到多个地点，同时缺货会造成不可逆的服务损失。为了研究这一问题，我们引入了在线共享库存分配（OSSA）问题，这是一种状态相关的在线模型，其中中央枢纽在固定运输成本和缺货惩罚下，将有限且未知的库存分配给面临顺序需求的多站点。与经典的生产备货或按单生产库存模型不同，OSSA 不允许积压订单，且补充库存仅能对冲未来需求。为了解决 OSSA 问题，我们提出了一种确定性的阈值比例策略 GPA，并证明其相对于离线最优解能达到 $4/3$ 的近似比（允许一个与总库存无关的加法项）。我们通过匹配的上下界补充了这一结果，表明即使对于预先知晓总库存的随机化算法，$4/3$ 的比率也是紧确的，且加法误差依赖性不可避免。最后，我们开发了 GPA 的学习增强型扩展版本，主要结合实践中常见的不完美预测（例如来自人类专家或机器学习模型的建议），使我们能够利用高质量建议的同时，对任意劣质建议保持鲁棒性。合成数据和真实世界的实验表明，当全局库存稀缺时，GPA 的性能优于自然基线方法。
查看原文
查看缓存全文

缓存时间: 2026/05/11 07:12 

# 具有未知共享供应量的在线分配
来源：https://arxiv.org/abs/2605.07080
查看 PDF (https://arxiv.org/pdf/2605.07080)

> 摘要：许多现实世界的资源分配系统，如人道主义物流和疫苗分配，必须在需求实现之前将有限的供应量预先部署到多个地点，而库存短缺会导致不可逆的服务损失。为了研究这一问题，我们引入了在线共享供应分配（OSSA）问题，这是一种有状态的在线模型，其中中央枢纽将有限且未知的供应量分配给面临顺序需求并产生固定运输成本和缺货惩罚的多个站点。与经典的备货制或订货制库存模型不同，OSSA 不允许延迟交货（backlogging），补货仅作为对未来需求的对冲。为了解决 OSSA 问题，我们提出了一种确定性的阈值比例策略 GPA，并证明其在离线最优解上达到了 $4/3$ 的近似比（加上一个与总供应量无关的加法项）。我们通过匹配的 lower bounds 补充了这一结果，表明即使在预先知道总供应量的随机化算法中，$4/3$ 的比率是紧的，且加法误差依赖性是不可避免的。最后，我们开发了 GPA 的增强学习扩展版本，主要结合了实践中常见的不完美预测（例如，来自人类专家或机器学习模型），使我们能够利用高质量建议，同时对任意糟糕的建议保持鲁棒性。合成和真实世界的实验表明，当全局供应量稀缺时，GPA 优于自然基线。

## 提交历史

来自：Davin Choo [查看邮箱 (https://arxiv.org/show-email/9fc0bcfc/2605.07080)] **[v1]** 2026年5月8日 星期五 00:59:11 UTC（5,184 KB）

相似文章

GAGPO：广义优势分组策略优化

arXiv cs.AI

GAGPO提出了一种无评论家的强化学习方法，在多方交互的自主任务中，利用非参数分组价值代理进行步级信用分配，在ALFWorld和WebShop上超越了强基线模型。

面向动态UBSR度量的MDPs在线策略评估

arXiv cs.LG

本文提出了在线学习算法，用于在线性函数近似下、具有动态效用型短缺风险（UBSR）度量的MDPs中进行高效的策略评估。引入了UBSR-TD算法，并证明了其收敛性和实际有效性。

具有有界采样违规的分布式在线赌博机子模最大化

arXiv cs.LG

本文提出了一种统一的算法框架，用于在划分拟阵约束下的分布式在线子模最大化，在完全信息和赌博机反馈两种情况下均实现了次线性 (1-1/e)-遗憾保证。此外，还引入了一种有界随机管道取整方案，以确保累积采样违规保持次线性。