论文标题
在线最低分页
Online Min-Max Paging
论文作者
论文摘要
在通信网络中的公平要求中，我们引入了在线分页问题的自然变体，称为\ textit {min-max}分页，其目的是最大程度地减少任何页面上的最大故障数量。虽然其目标是最大程度地减少故障总数，但承认$ k $竞争性的确定性和$ o（\ log k）$ - 竞争性随机算法，但我们表明，Min-Max分页不承认$ C（K）$ - 对任何功能$ C $ $ c $ $ c $ $ c（k）$ - 竞争性算法。具体而言，我们证明，最低最大分页的随机竞争比为$ω（\ log（n））$，其确定性竞争比为$ω（k \ log（n）/\ log（k））$，其中$ n $是$ n $的总数。 我们设计了一个针对分页的分数算法，该算法具有一个更一般的目标 - 最大程度地减少了应用于每个页面上故障数量的向量的$ n $变量可区分凸功能的值。这给出了$ O（\ log（n）\ log（k））$ - 竞争性分数算法用于Min-Max分页。我们展示了如何将这种分数算法围绕竞争比最多最多$ k $因子损失，从而导致确定性的$ O（k \ log（n）\ log（k））$ - 最小值分页的竞争性算法。这匹配我们的下边界Modulo a $ \ mathrm {poly}（\ log（k））$ factor。我们还提供了一种随机的圆形算法，该算法会导致$ O（\ log^2 n \ log k）$ - 竞争算法。
Motivated by fairness requirements in communication networks, we introduce a natural variant of the online paging problem, called \textit{min-max} paging, where the objective is to minimize the maximum number of faults on any page. While the classical paging problem, whose objective is to minimize the total number of faults, admits $k$-competitive deterministic and $O(\log k)$-competitive randomized algorithms, we show that min-max paging does not admit a $c(k)$-competitive algorithm for any function $c$. Specifically, we prove that the randomized competitive ratio of min-max paging is $Ω(\log(n))$ and its deterministic competitive ratio is $Ω(k\log(n)/\log(k))$, where $n$ is the total number of pages ever requested. We design a fractional algorithm for paging with a more general objective -- minimize the value of an $n$-variate differentiable convex function applied to the vector of the number of faults on each page. This gives an $O(\log(n)\log(k))$-competitive fractional algorithm for min-max paging. We show how to round such a fractional algorithm with at most a $k$ factor loss in the competitive ratio, resulting in a deterministic $O(k\log(n)\log(k))$-competitive algorithm for min-max paging. This matches our lower bound modulo a $\mathrm{poly}(\log(k))$ factor. We also give a randomized rounding algorithm that results in a $O(\log^2 n \log k)$-competitive algorithm.
