Competitive analysis of the top-K ranking problem
Competitive analysis of the top-K ranking problem
复制标题
DOI：
10.1137/1.9781611974782.81
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Xi Chen;Sivakanth Gopi;Jieming Mao;Jon Schneider
中科院分区：
文献类型：
--
作者：
Xi Chen;Sivakanth Gopi;Jieming Mao;Jon Schneider
受推荐系统、网络搜索、社交选择和众包等应用的启发，我们考虑了从噪声的两两比较中识别前K项集合的问题。在我们的设置中，我们被非主动地给予每对n项之间的r个成对比较，其中每个比较都具有被称为强随机传递性(SST)模型的非常一般的噪声模型约束的噪声。分析了算法对TOP-K问题的竞争比。特别地，我们给出了一个求解竞争比为O(√n)的TOP-K问题的线性时间算法，即要求解任何一个TOP-K实例，我们的算法所需的样本数至多是该实例的最佳可能算法的O(√n)倍(相比之下，所有已知的TOP-K问题的算法都具有Ω(N)或更差的竞争比)。我们进一步证明了这是紧的：解TOP-K问题的任何算法都有至少Ω(√n的竞争比。普林斯顿大学斯特恩商学院计算机科学系电子邮件：sgopi@cs.princeton.edu电子邮件：jiemingm@cs.princeton.edu普林斯顿大学计算机科学系
Motivated by applications in recommender systems, web search, social choice and crowdsourcing, we consider the problem of identifying the set of top K items from noisy pairwise comparisons. In our setting, we are non-actively given r pairwise comparisons between each pair of n items, where each comparison has noise constrained by a very general noise model called the strong stochastic transitivity (SST) model. We analyze the competitive ratio of algorithms for the top-K problem. In particular, we present a linear time algorithm for the top-K problem which has a competitive ratio of O( √ n); i.e. to solve any instance of top-K, our algorithm needs at most O( √ n) times as many samples needed as the best possible algorithm for that instance (in contrast, all previous known algorithms for the top-K problem have competitive ratios of Ω(n) or worse). We further show that this is tight: any algorithm for the top-K problem has competitive ratio at least Ω( √ n). Stern School of Business, New York University, email: xchen3@stern.nyu.edu Department of Computer Science, Princeton University, email: sgopi@cs.princeton.edu Department of Computer Science, Princeton University, email: jiemingm@cs.princeton.edu Department of Computer Science, Princeton University, email: js44@cs.princeton.edu 1