论文标题
改进的在线Min-sum套装的算法
An Improved Algorithm For Online Min-Sum Set Cover
论文作者
论文摘要
我们研究了在线偏好聚合的基本模型，其中算法保留了$ n $元素的有序列表。输入是首选集$ r_1，r_2，\ dots，r_t，\ dots $的流。在看到$ r_t $并且在不了解未来集合的情况下，必须将算法重新读取元素（更改列表订购），以便至少在列表附近找到$ r_t $的一个元素。所产生的成本是列表更新成本（相邻列表元素的掉期数量）和访问成本（列表中$ r_t $的第一个元素的位置）的总和。这种情况自然发生在诸如使用商店客户汇总的偏好中在线商店订购的应用程序中。该问题的理论基础称为Min-sum集盖。 与以前的工作（Fotakis等人，ICALP 2020，NIPS 2020）不同，主要研究了针对静态最佳解决方案的在线算法ALG的性能（单个最佳列表订购），在本文中，我们研究了一个可以说的更难的变体，其中可证明的基准是可以证明是强大的动态解决方案（也可以选择列表）。就在线商店而言，这意味着其用户群的汇总偏好随时间发展。我们构建了一种计算高效的随机算法，其竞争比（alg-opt成本比）为$ O（r^2）$，并证明存在确定性$ O（r^4）$ - 竞争算法。在这里，$ r $是集合$ r_t $的最大基数。这是第一个算法，其比率不依赖于$ n $：此问题的先前最佳算法为$ O（r^{3/2} \ cdot \ sqrt {n}）$ - 竞争性和$ω（r）$是任何确定性在线算法的较低限制。
We study a fundamental model of online preference aggregation, where an algorithm maintains an ordered list of $n$ elements. An input is a stream of preferred sets $R_1, R_2, \dots, R_t, \dots$. Upon seeing $R_t$ and without knowledge of any future sets, an algorithm has to rerank elements (change the list ordering), so that at least one element of $R_t$ is found near the list front. The incurred cost is a sum of the list update costs (the number of swaps of neighboring list elements) and access costs (position of the first element of $R_t$ on the list). This scenario occurs naturally in applications such as ordering items in an online shop using aggregated preferences of shop customers. The theoretical underpinning of this problem is known as Min-Sum Set Cover. Unlike previous work (Fotakis et al., ICALP 2020, NIPS 2020) that mostly studied the performance of an online algorithm ALG against the static optimal solution (a single optimal list ordering), in this paper, we study an arguably harder variant where the benchmark is the provably stronger optimal dynamic solution OPT (that may also modify the list ordering). In terms of an online shop, this means that the aggregated preferences of its user base evolve with time. We construct a computationally efficient randomized algorithm whose competitive ratio (ALG-to-OPT cost ratio) is $O(r^2)$ and prove the existence of a deterministic $O(r^4)$-competitive algorithm. Here, $r$ is the maximum cardinality of sets $R_t$. This is the first algorithm whose ratio does not depend on $n$: the previously best algorithm for this problem was $O(r^{3/2} \cdot \sqrt{n})$-competitive and $Ω(r)$ is a lower bound on the performance of any deterministic online algorithm.
