Sorting with Recurrent Comparison Errors

DOI10.4230/LIPICS.ISAAC.2017.38MaRDI QIDQ5136257zbMATH OpenOpenAlexFDO

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

Publication date 25 November 2020

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

zbMATH Keywords

maximum and total dislocationrecurrent comparison errorsorting

Mathematics Subject Classification ID

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

Abstract: We present a sorting algorithm for the case of recurrent random comparison errors. The algorithm essentially achieves simultaneously good properties of previous algorithms for sorting $n$ distinct elements in this model. In particular, it runs in $O(n^2)$ time, the maximum dislocation of the elements in the output is $O(logn)$, while the total dislocation is $O(n)$. These guarantees are the best possible since we prove that even randomized algorithms cannot achieve $o(logn)$ maximum dislocation with high probability, or $o(n)$ total dislocation in expectation, regardless of their running time.

Recommendations

• Optimal sorting with persistent comparison errors
• Recursive merge sort with erroneous comparisons
• The solution space of sorting with recurring comparison faults
• The solution space of sorting with recurring comparison faults
• Recurring comparison faults: sorting and finding the minimum
• Measures of disorder and straight insertion sort with erroneous comparisons
• Sorting with expensive comparands
• On the distribution of comparisons in sorting algorithms

Cites work

• Computing with Noisy Information
• Fault-tolerant search algorithms. Reliable computation with unreliable information
• scientific article; zbMATH DE number 3584785 (Why is no real title available?)
• Introduction to algorithms.
• Noisy binary search and its applications
• Noisy sorting without resampling
• Ordering by weighted number of wins gives a good ranking for weighted tournaments
• Probability and Computing
• Quicksort with Unreliable Comparisons: A Probabilistic Analysis
• Recursive merge sort with erroneous comparisons
• Searching games with errors -- fifty years of coping with liars
• The solution space of sorting with recurring comparison faults
• Tolerant algorithms

Cited in

(18)

• On sorting in the presence of erroneous information
• Sorting by swaps with noisy comparisons
• Optimal dislocation with persistent errors in subquadratic time
• Approximate minimum selection with unreliable comparisons
• The solution space of sorting with recurring comparison faults
• Recurring comparison faults: sorting and finding the minimum
• Optimal dislocation with persistent errors in subquadratic time
• scientific article; zbMATH DE number 8118 (Why is no real title available?)
• scientific article; zbMATH DE number 2147931 (Why is no real title available?)
• Optimal sorting with persistent comparison errors
• Resilient Dictionaries for Randomly Unreliable Memory
• Inversions from sorting with distance-based errors
• Approximate Sorting
• Approximate Sorting
• External-memory sorting with comparison errors
• Recursive merge sort with erroneous comparisons
• Approximate selection with unreliable comparisons in sublinear time
• Making bubblesort recursive

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

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