论文标题
在线序数问题：基于比较的算法及其基本复杂性的最佳性
Online Ordinal Problems: Optimality of Comparison-based Algorithms and their Cardinal Complexity
论文作者
论文摘要
我们考虑在线问题，即仅需要在输入元素之间进行成对比较的任务。一个经典的例子是秘书问题和Googol的游戏，以及其多个组合扩展名，例如$（j，k）$ - 秘书，$ 2 $的Googol游戏，Oldinal竞争性的Matroid秘书。这些任务的一种自然方法是使用序数算法，在每个步骤中仅考虑到达元素之间的相对排名，而无需查看输入的数值。我们正式研究了基本算法如何在顺序算法上改善的问题。 我们首先为任何序数在线问题提供了通用的输入分布的构造，因此，对于任意的小$ \ varepsilon> 0 $，任何基本算法比序列算法的优势最多为$ 1+\ varepsilon $。这意味着，上述秘书问题变体的先前下限不仅符合序数算法，而且还符合任何在线算法。但是，我们结构中输入元素的值范围很大：$ n = o \ left（\ frac {n^3 \ cdot n！\ cdot n！} {\ varepsilon} \ right）\ uperarow \ uparrow \ uparrow \ uparrow \ uparrow（n-1）$（tower of enperents of Exporents for length of Lengthe fortep of长度$ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n。作为第二个结果，我们确定了一类自然序数问题，并找到具有$ 1+ω\ left（\ frac {1} {\ log^{（c）} n} \ right）的匹配优势的基本算法，其中$ \ log log^{（c）n = \ log \ log \ log \ ldots untantial $ co.此外，我们针对任何给定的序数在线任务介绍了基本复杂性：输入中不同数值的最小尺寸$ n（\ varepsilon）$，基于序数算法的优势最多是$ 1+\ varepsilon $。作为第三个结果，我们表明Googol的游戏具有较低的基数复杂度，为$ n = o \ left（\ left（\ frac {n} {\ varepsilon} \ right）^n \ right）$。
We consider ordinal online problems, i.e., tasks that only require pairwise comparisons between elements of the input. A classic example is the secretary problem and the game of googol, as well as its multiple combinatorial extensions such as $(J,K)$-secretary, $2$-sided game of googol, ordinal-competitive matroid secretary. A natural approach to these tasks is to use ordinal algorithms that at each step only consider relative ranking among the arrived elements, without looking at the numerical values of the input. We formally study the question of how cardinal algorithms can improve upon ordinal algorithms. We give first a universal construction of the input distribution for any ordinal online problem, such that the advantage of any cardinal algorithm over the ordinal algorithms is at most $1+\varepsilon$ for arbitrary small $\varepsilon> 0$. As an implication, previous lower bounds for the aforementioned variants of secretary problems hold not only against ordinal algorithms, but also against any online algorithm. However, the value range of the input elements in our construction is huge: $N=O\left(\frac{n^3\cdot n!\cdot n!}{\varepsilon}\right)\uparrow\uparrow(n-1)$ (tower of exponents) for an input sequence of length $n$. As a second result, we identify a class of natural ordinal problems and find cardinal algorithm with a matching advantage of $1+ Ω\left(\frac{1}{\log^{(c)}N}\right),$ where $\log^{(c)}N=\log\ldots\log N$ with $c$ iterative logs and $c$ is an arbitrary constant. Further, we introduce the cardinal complexity for any given ordinal online task: the minimum size $N(\varepsilon)$ of different numerical values in the input such the advantage of cardinal over ordinal algorithms is at most $1+\varepsilon$. As a third result, we show that the game of googol has much lower cardinal complexity of $N=O\left(\left(\frac{n}{\varepsilon}\right)^n\right)$.
