文件名称：使用可重用资源进行在线分类优化-研究论文
文件大小：419KB
文件格式：PDF
更新时间：2024-06-29 08:45:42
Online Algorithms Assortment
我们考虑一个在线分类优化问题，其中我们有 n 个具有固定可重复使用容量 c1,...,cn 的可替代产品。 在每个时间段 t，具有某些偏好（可能被敌对选择）的用户到达卖家平台，该平台提供可用产品集中的产品子集 St。 用户以偏好模型给定的概率选择产品 j ∈ St，并将其用于随机数量的时期， ˜ tj 根据某些分布分配 iid，该分布仅依赖于 j 为卖家产生收入 rj(˜ tj) . 卖家的目标是找到一个策略，在有限的时间范围 T 内最大化预期累积。我们在本文中的主要贡献是展示了一个简单的近视策略（我们从可用产品中向每个用户提供近视最优分类) 为问题提供了一个很好的近似。 特别地，我们证明了近视策略是 1/2 竞争的，即近视策略的预期累积收入至少是具有用户偏好序列的完整信息的最优策略的预期收入的 1/2 倍所有产品的型号和随机使用时间的分布。 相比之下，近视策略不需要任何关于未来到达或随机使用时间分布的信息。 该分析基于耦合参数，该参数允许我们根据近视策略的预期收入来限制最优算法的预期收入。 我们还考虑了使用时间分布取决于每个用户类型的设置，并表明在这种更一般的情况下，没有具有非平凡竞争比率保证的在线算法。 最后，我们进行数值实验以比较近视策略与其他自然策略的稳健性和性能。