We present the first randomized upper and lower bounds for online multi-threaded paging as introduced by Feuerstein and Strejilevich de Loma [5]. Our main result is a O(w log k)-competitive algorithm for unfair infinite multi-threaded paging, which is optimal to within a constant factor. We also present algorithms and lower bounds for three other sub-models for multi-threaded paging.
展开▼
机译：我们介绍了Feuerstein和Strejilevich de Loma [5]提出的在线多线程寻呼的第一个随机上限和下限。我们的主要结果是针对不公平的无限多线程分页的O（w log k）竞争算法，该算法在恒定因子内是最佳的。我们还介绍了用于多线程分页的其他三个子模型的算法和下界。
展开▼
