文件名称：外源补货的可重用资源在线分类-研究论文
文件大小：687KB
文件格式：PDF
更新时间：2024-06-29 23:50:57
论文研究
我们介绍并研究了一种在线分类规划的变体，其中产品用于出租——与更经典的产品出售模型形成对比——并且它们的库存会随着时间的推移而补充。 这个问题部分是由 Thumbtack 或 Catchafire 等用于分配租赁服务的在线平台引起的，随着时间的推移，额外的劳动力或志愿者可以为特定服务或产品的库存充值。 在线平台的目标是依次选择分类以最大化分配产品的总租金奖励（其中奖励可以解释为费用或任何其他类型的分数）。 对于消费者和补货金额预先未知的在线（对抗性）设置，我们设计了一个新的算法系列，我们称之为批量库存平衡 (BIB)。 通过扩展不可重复使用的在线分类问题的框架，我们开发了一种新的随机原始对偶方法，将我们的 BIB 算法的竞争比率与任何可行的策略相结合，以最大化收集的总租金奖励。 我们以适当的选择表明某个参数，这种竞争比率是渐近的最佳和收敛到（1-1 / e），因为初始库存会聚到无穷大。 然后，我们将展示如何以“一般”形式描述 BIB 的竞争比率。 我们使用一种精细的分析，将对偶构造简化为称为“区间分配问题”的组合问题。 我们对这个问题的解决方案是算法的，可能是独立的。