文件名称：任意到达下的在线资源分配：最优算法和严格的竞争比率-研究论文
文件大小：884KB
文件格式：PDF
更新时间：2024-06-29 06:53:03
Online Algorithms Competitive
受电子商务中出现的动态分类产品和商品定价的启发，我们研究了将有限库存分配给顺序到达的异构客户的一般问题。 我们在竞争分析的框架下分析这个问题，其中客户的顺序是未知的，不一定遵循任何模式。 该领域以前的工作，研究在线匹配、广告和分类问题，主要关注每件商品只能以单一价格出售的情况，从而产生了实现 1-1/e 的最佳竞争比率的算法.在本文中，我们扩展了所有这些结果以允许具有多个可行价格的项目。 我们的算法实现了最可能的权重相关竞争比率，这取决于预先给出的可行价格集。 我们的算法也简单直观； 它们基于构建一类通用的“价值函数”，它集成了项目的选择和提供的价格。最后，我们在 Bodea 等人的公开酒店数据集上测试我们的算法。 (2009)，其中有多个项目（酒店房间），每个项目都有多个价格（可以出售房间的票价）。 我们发现，将我们的算法与试图预测和学习未来交易的算法“混合”应用，会产生最佳性能。