Competitive analysis of the top-K ranking problem

DOI10.1137/1.9781611974782.81zbMath1410.68339arXiv1605.03933OpenAlexW2362096638MaRDI QIDQ4575824

Xi Chen, Jon Schneider, Jieming Mao, Sivakanth Gopi

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1605.03933

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (12)

Low Permutation-rank Matrices: Structural Properties and Noisy Completion ⋮ Top-\(\kappa\) selection with pairwise comparisons ⋮ Partial recovery for top-\(k\) ranking: optimality of MLE and suboptimality of the spectral method ⋮ Optimal full ranking from pairwise comparisons ⋮ Ranking and selection for pairwise comparison ⋮ Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees ⋮ Worst-case versus average-case design for estimation from partial pairwise comparisons ⋮ Active ranking from pairwise comparisons and when parametric assumptions do not help ⋮ Spectral method and regularized MLE are both optimal for top-\(K\) ranking ⋮ Approximate minimum selection with unreliable comparisons ⋮ Unnamed Item ⋮ Time-homogeneous top-K ranking using tensor decompositions

This page was built for publication: Competitive analysis of the top-K ranking problem