Maximum Selection and Sorting with Adversarial Comparators
Maximum Selection and Sorting with Adversarial Comparators
复制标题
使用对抗性比较器进行最大选择和排序
DOI：
--
复制
发表时间：
2018
影响因子：
6
通讯作者：
A. Suresh
中科院分区：
文献类型：
--
作者：
Jayadev Acharya;Moein Falahatgar;Ashkan Jafarpour;A. Orlitsky;A. Suresh
我们研究最大选择和排序的n个数字使用不完美的两两比较。如果两个输入之间的距离大于给定阈值，则不完美比较器返回两个输入中较大的一个，否则返回相反选择的输入。我们考虑两个对抗模型：一个非自适应对手，提前决定的结果和一个自适应对手，根据以前的比较和结果决定每次比较的结果。对非自适应对手，我们得出一个最大选择算法，使用最多2n比较的期望和排序算法，使用最多2n LNN比较的期望。在存在自适应对手的情况下，所提出的最大选择算法使用Θ（n log（1/））比较来输出概率至少为1−的正确答案，解决了Ajtai et al.（2015）中的一个开放问题。我们的研究是出于密度估计问题。给定来自未知分布的样本，我们希望在n个候选分布的已知类别中找到一个分布，该分布以'1距离接近底层分布。Scheffe的算法，例如，在Devroye和Lugosi（2001）中，输出最多9倍于最小值的`1距离处的分布，并在时间Θ（n log n）中运行。使用我们的算法，运行时间减少到Θ（n log n）。
We study maximum selection and sorting of n numbers using imperfect pairwise comparators. The imperfect comparator returns the larger of the two inputs if the inputs are more than a given threshold apart and an adversarially-chosen input otherwise. We consider two adversarial models: a non-adaptive adversary that decides on the outcomes in advance and an adaptive adversary that decides on the outcome of each comparison depending on the previous comparisons and outcomes. Against the non-adaptive adversary, we derive a maximum-selection algorithm that uses at most 2n comparisons in expectation and a sorting algorithm that uses at most 2n lnn comparisons in expectation. In the presence of the adaptive adversary, the proposed maximum-selection algorithm uses Θ(n log(1/ )) comparisons to output a correct answer with probability at least 1− , resolving an open problem in Ajtai et al. (2015). Our study is motivated by a density-estimation problem. Given samples from an unknown distribution, we would like to find a distribution among a known class of n candidate distributions that is close to the underlying distribution in `1 distance. Scheffe’s algorithm, for example, in Devroye and Lugosi (2001) outputs a distribution at an `1 distance at most 9 times the minimum and runs in time Θ(n log n). Using our algorithm, the runtime reduces to Θ(n log n).