论文标题
随机阶模型
Random-Order Models
论文作者
论文摘要
本章在线算法中介绍了\ emph {Random-order模型}。在此模型中，输入是由对手选择的，然后随机置换在算法之前。这种改组通常会削弱对手的力量，并可以改善算法保证。我们显示了两个广泛的问题的改进：包装问题，我们必须选择一组受约束的项目以最大化总价值，并涵盖我们必须以最低总成本满足给定要求的问题。我们还讨论了随机阶模型与用于非智障竞争分析的其他随机模型的关系。
This chapter introduces the \emph{random-order model} in online algorithms. In this model, the input is chosen by an adversary, then randomly permuted before being presented to the algorithm. This reshuffling often weakens the power of the adversary and allows for improved algorithmic guarantees. We show such improvements for two broad classes of problems: packing problems where we must pick a constrained set of items to maximize total value, and covering problems where we must satisfy given requirements at minimum total cost. We also discuss how random-order model relates to other stochastic models used for non-worst-case competitive analysis.
