Sorting with Recurrent Comparison Errors

DOI10.4230/LIPIcs.ISAAC.2017.38zbMath1457.68077arXiv1709.07249OpenAlexW2962892929MaRDI QIDQ5136257

Chih-Hung Liu, Stefano Leucci, Paolo Penna, Barbara Geissmann

Publication date: 25 November 2020

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

zbMATH Keywords

sortingmaximum and total dislocationrecurrent comparison error

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10)

Related Items (6)

External-memory sorting with comparison errors ⋮ Optimal dislocation with persistent errors in subquadratic time ⋮ Unnamed Item ⋮ Longest increasing subsequence under persistent comparison errors ⋮ Resilient Dictionaries for Randomly Unreliable Memory ⋮ Approximate minimum selection with unreliable comparisons

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fault-tolerant search algorithms. Reliable computation with unreliable information
• Recursive merge sort with erroneous comparisons
• The Solution Space of Sorting with Recurring Comparison Faults
• Tolerant Algorithms
• Computing with Noisy Information
• Quicksort with Unreliable Comparisons: A Probabilistic Analysis
• Probability and Computing
• Ordering by weighted number of wins gives a good ranking for weighted tournaments
• Searching games with errors -- fifty years of coping with liars

This page was built for publication: Sorting with Recurrent Comparison Errors