Sorting and Selection with Imprecise Comparisons

DOI10.1007/978-3-642-02927-1_5zbMath1248.68177arXiv1501.02911OpenAlexW2342402489MaRDI QIDQ3638022

Avinatan Hassidim, Miklós Ajtai, Vitaly Feldman, Jelani Nelson

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

zbMATH Keywords

sortingselectionmaximumpaired comparisonsWeber's lawjust noticeable differencefaulty comparisonstournament king

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (16)

Query-competitive sorting with uncertainty ⋮ Optimal Dislocation with Persistent Errors in Subquadratic Time ⋮ Partial sorting problem on evolving data ⋮ On the optimality of tape merge of two lists with similar size ⋮ Energy efficient sorting, selection and searching ⋮ Round-competitive algorithms for uncertainty problems with parallel queries ⋮ The Complexity of Finding (Approximate Sized) Distance-d Dominating Set in Tournaments ⋮ Optimal dislocation with persistent errors in subquadratic time ⋮ Resilient dynamic programming ⋮ Unnamed Item ⋮ Longest increasing subsequence under persistent comparison errors ⋮ Query minimization under stochastic uncertainty ⋮ Query-Competitive Sorting with Uncertainty. ⋮ On the Evolution of Monotone Conjunctions: Drilling for Best Approximations ⋮ Unnamed Item ⋮ Finding kings in tournaments

This page was built for publication: Sorting and Selection with Imprecise Comparisons