我们研究了受到铁路票务和酒店房间预订等应用启发的网络收入管理问题。请求依次到达，每个请求要求连续占用资源，且到达概率已知。我们探讨了两种情景：接受或拒绝情景，在此情景中，任何可用资源都可以满足请求；以及基于基本吸引模型（BAM）的情景，后者通过客户偏好来推广前者，允许平台提供可供客户选择的可用资源。
在此基础上，我们开发了多项式时间策略，并通过近似比来评估其性能，近似比定义为我们策略的预期收入与最佳在线算法的收入之比。当每个到达请求具有固定类型（例如，入住时间间隔固定）时，我们建立了常数因子保证：接受或拒绝情景的比率为 $1 - 1/e$，而 BAM 基础场景的比率为 $0.25$。
我们进一步将这些结果扩展到请求类型随机的情况（例如，入住时间间隔随机）。在此设置下，近似比额外引入了 $1 - 1/e$ 的乘法因子，从而在接受或拒绝情景中保证至少 $0.399$，而在 BAM 基础场景中保证至少 $0.156$。这些常数因子保证与之前相对于离线最优的非常数竞争比形成鲜明对比。
博主点评： 本文通过对收入管理问题的深入分析，提出了有效的算法策略，尤其是在随机请求情况下的应用，展示了理论与实践结合的潜力。常数因子保证不仅提高了收益预测的准确性，更为实际应用提供了有力支持，值得关注和深入研究。