文件名称:近乎最优的贝叶斯在线可重用资源分类-研究论文
文件大小:1.02MB
文件格式:PDF
更新时间:2024-06-29 20:43:21
Assortment optimization Online
受租赁服务在电子商务中的应用的启发,我们考虑为不同类型的到达消费者提供可重复使用资源的在线分类的收入最大化。 我们针对贝叶斯设置中的最佳在线策略设计了具有竞争力的在线算法,其中类型随着时间的推移独立于已知的异构分布。 在初始库存的最小值 c_min 很大的情况下,我们的主要结果是针对可重用资源的一般情况的近乎最优的 1-min(1/2,\sqrt{log(c_min)/c_min}) 竞争算法。 对于不可重用资源的特殊情况,我们进一步展示了改进的近最优 1-1/\sqrt{c_min+3} 竞争算法。 我们的算法依赖于问题的预期 LP 基准,解决这个 LP,并通过独立的随机舍入模拟解决方案。 为了从这些基于模拟的算法中以计算效率高的方式获得逐点库存可行性,我们使用多种技术成分来设计“丢弃策略”——每个资源一个。 这些策略处理可重用性下的库存可行性与每个资源的收入损失之间的权衡。 我们还引入了后处理分类程序,帮助设计和分析我们的丢弃政策,这可能具有独立的利益。 我们最终使用对合成数据的模拟来评估我们算法的性能。