Optimal sorting with persistent comparison errors

DOI10.4230/LIPICS.ESA.2019.49MaRDI QIDQ5075792zbMATH OpenFDO

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

Publication date 11 May 2022

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

zbMATH Keywords

approximate sortingcomparison errorspersistent errors

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Optimal dislocation with persistent errors in subquadratic time
• Optimal dislocation with persistent errors in subquadratic time
• Sorting with Recurrent Comparison Errors
• On sorting in the presence of erroneous information

Cites work

• scientific article; zbMATH DE number 3547240 (Why is no real title available?)
• scientific article; zbMATH DE number 3205803 (Why is no real title available?)
• Computing with Noisy Information
• Coping with errors in binary search procedures
• Fault-tolerant search algorithms. Reliable computation with unreliable information
• Noisy sorting without resampling
• Optimal dislocation with persistent errors in subquadratic time
• Parallel algorithms for select and partition with noisy comparisons
• Quicksort with Unreliable Comparisons: A Probabilistic Analysis
• Recursive merge sort with erroneous comparisons
• Searching games with errors -- fifty years of coping with liars
• Sorting from Noisier Samples
• Sorting with Recurrent Comparison Errors
• The solution space of sorting with recurring comparison faults
• Tolerant algorithms

This page was built for publication: Optimal sorting with persistent comparison errors

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