Approximate selection with unreliable comparisons in sublinear time

DOI10.1016/J.JCSS.2025.103699MaRDI QIDQ6924402zbMATH OpenFDO

Authors Shengyu Huang, Chih-Hung Liu, Daniel Rutschmann

Publication date 29 September 2025

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2025.103699

zbMATH Keywords

approximate selectionrandom comparison faultsrandomized algorithmsunreliable comparisons

Mathematics Subject Classification ID

Searching and sorting (68P10) Randomized algorithms (68W20)

Cites work

• Aggregating inconsistent information: ranking and clustering
• Amplification and Derandomization without Slowdown
• Approximate minimum selection with unreliable comparisons
• Approximate selection with unreliable comparisons in optimal expected time
• Comparison-based search in the presence of errors
• Competitive analysis of the top-K ranking problem
• Computing with Noisy Information
• Energy efficient sorting, selection and searching
• External-memory sorting with comparison errors
• Fast FAST
• Fault-tolerant search algorithms. Reliable computation with unreliable information
• Finding the maximum and minimum
• scientific article; zbMATH DE number 5485441 (Why is no real title available?)
• scientific article; zbMATH DE number 4033104 (Why is no real title available?)
• scientific article; zbMATH DE number 7650297 (Why is no real title available?)
• Longest increasing subsequence under persistent comparison errors
• Noisy binary search and its applications
• Noisy sorting without resampling
• On sorting in the presence of erroneous information
• Optimal Bounds for Noisy Sorting
• Optimal dislocation with persistent errors in subquadratic time
• Optimal resilient sorting and searching in the presence of memory faults
• Optimal sorting with persistent comparison errors
• Parallel algorithms for select and partition with noisy comparisons
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Ranking Tournaments
• Resilient dictionaries
• Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees
• Searching games with errors -- fifty years of coping with liars
• Searching with known error probability
• Sorting and searching in faulty memories
• Sorting noisy data with partial information
• Sorting with Recurrent Comparison Errors
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Tolerant algorithms

This page was built for publication: Approximate selection with unreliable comparisons in sublinear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6924402)