Approximate minimum selection with unreliable comparisons

DOI10.1007/s00453-021-00880-1OpenAlexW3209836283MaRDI QIDQ2072098

Stefano Leucci, Chih-Hung Liu

Publication date: 1 February 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-021-00880-1

zbMATH Keywords

independent errorsapproximate minimum selectionunreliable comparisons

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (1)

Energy efficient sorting, selection and searching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fault-tolerant search algorithms. Reliable computation with unreliable information
• Finding the maximum and minimum
• Optimal resilient sorting and searching in the presence of memory faults
• Searching with known error probability
• Coping with errors in binary search procedures
• On sorting in the presence of erroneous information
• Optimal dislocation with persistent errors in subquadratic time
• Recurring Comparison Faults: Sorting and Finding the Minimum
• Sorting noisy data with partial information
• Tolerant Algorithms
• Tight Bounds on the Size of Fault-Tolerant Merging and Sorting Networks with Destructive Faults
• Computing with Noisy Information
• Competitive analysis of the top-K ranking problem
• Staircase Series
• Resilient Dictionaries for Randomly Unreliable Memory
• Sorting with Recurrent Comparison Errors
• Comparison-based search in the presence of errors
• Parallel algorithms for select and partition with noisy comparisons
• Searching games with errors -- fifty years of coping with liars

This page was built for publication: Approximate minimum selection with unreliable comparisons