Sorting and Selection with Imprecise Comparisons
From MaRDI portal
Publication:3638022
DOI10.1007/978-3-642-02927-1_5zbMath1248.68177arXiv1501.02911MaRDI QIDQ3638022
Vitaly Feldman, Jelani Nelson, Miklós Ajtai, Avinatan Hassidim
Publication date: 14 July 2009
Published in: ACM Transactions on Algorithms, Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1501.02911
sorting; selection; maximum; paired comparisons; Weber's law; just noticeable difference; faulty comparisons; tournament king
68Q25: Analysis of algorithms and problem complexity
68P10: Searching and sorting
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)