论文标题
在线Min-sum设定封面问题
The Online Min-Sum Set Cover Problem
论文作者
论文摘要
我们考虑在线Min-sum Set Cover（MSSC），这是对经典列表更新问题的自然而有趣的概括。在在线MSSC中，该算法在基于子集$ s_1，s_2，\ ldots $到达在线的$ n $元素上保持了排列。该算法使用其当前排列$π_{t} $在到达时为每个集合$ s_t $服务，产生的访问成本等于$ s_t $ in $π_{t} $的第一个元素的位置。然后，算法可能将其置换量更新为$π_{t+1} $，产生的移动成本等于$π_{t} $的kendall tau距离为$π_{t+1} $。目的是最大程度地减少服务整个序列的总访问和移动成本。我们考虑了$ r $均匀的版本，其中每个$ s_t $都有基数$ r $。列表更新是$ r = 1 $的特殊情况。 我们获得了MSSC的确定性在线算法与静态对手的竞争比率的紧密界限，该算法通过单个置换来满足整个序列。首先，我们在竞争比率上显示了$（R+1）（1- \ frac {r} {n+1}）$的下限。然后，我们考虑了成功列表更新算法的几种自然概括，并表明它们无法获得任何有趣的竞争保证。从积极的一面来看，我们使用在线学习中的想法和乘法重量更新（MWU）算法获得了$ O（R）$ - 竞争性的确定性算法。 此外，我们考虑有效的算法。我们提出了一种无内存的在线算法，称为“全部移动”，该算法的灵感来自$ k $ server问题的双重覆盖算法。我们表明其竞争比为$ω（r^2）$和$ 2^{o（\ sqrt {\ log n \ cdot \ log r}）} $，并猜想是$ f（r）$ - 竞争性。我们还将移动的移动与动态最佳解决方案进行比较，并通过表明它为$ω（r \ sqrt {n}）$和$ O（r^{3/2} \ sqrt {n}）$，从而获得（几乎）紧密的边界。
We consider the online Min-Sum Set Cover (MSSC), a natural and intriguing generalization of the classical list update problem. In Online MSSC, the algorithm maintains a permutation on $n$ elements based on subsets $S_1, S_2, \ldots$ arriving online. The algorithm serves each set $S_t$ upon arrival, using its current permutation $π_{t}$, incurring an access cost equal to the position of the first element of $S_t$ in $π_{t}$. Then, the algorithm may update its permutation to $π_{t+1}$, incurring a moving cost equal to the Kendall tau distance of $π_{t}$ to $π_{t+1}$. The objective is to minimize the total access and moving cost for serving the entire sequence. We consider the $r$-uniform version, where each $S_t$ has cardinality $r$. List update is the special case where $r = 1$. We obtain tight bounds on the competitive ratio of deterministic online algorithms for MSSC against a static adversary, that serves the entire sequence by a single permutation. First, we show a lower bound of $(r+1)(1-\frac{r}{n+1})$ on the competitive ratio. Then, we consider several natural generalizations of successful list update algorithms and show that they fail to achieve any interesting competitive guarantee. On the positive side, we obtain a $O(r)$-competitive deterministic algorithm using ideas from online learning and the multiplicative weight updates (MWU) algorithm. Furthermore, we consider efficient algorithms. We propose a memoryless online algorithm, called Move-All-Equally, which is inspired by the Double Coverage algorithm for the $k$-server problem. We show that its competitive ratio is $Ω(r^2)$ and $2^{O(\sqrt{\log n \cdot \log r})}$, and conjecture that it is $f(r)$-competitive. We also compare Move-All-Equally against the dynamic optimal solution and obtain (almost) tight bounds by showing that it is $Ω(r \sqrt{n})$ and $O(r^{3/2} \sqrt{n})$-competitive.
