Optimal dislocation with persistent errors in subquadratic time
Journal
Leibniz International Proceedings in Informatics, LIPIcs
Journal Volume
96
Date Issued
2018
Author(s)
Abstract
We study the problem of sorting N elements in presence of persistent errors in comparisons: In this classical model, each comparison between two elements is wrong independently with some probability p, but repeating the same comparison gives always the same result. The best known algorithms for this problem have running time O(N2) and achieve an optimal maximum dislocation of O(log N) for constant error probability. Note that no algorithm can achieve dislocation o(log N), regardless of its running time. In this work we present the first subquadratic time algorithm with optimal maximum dislocation: Our algorithm runs in O(N3/2) time and guarantees O(log N) maximum dislocation with high probability. Though the first version of our algorithm is randomized, it can be derandomized by extracting the necessary random bits from the results of the comparisons (errors). © Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna.
Subjects
Maximum Dislocation; Recurrent Comparison Errors; Sorting
Other Subjects
Probability; Sorting; Best-known algorithms; Classical model; Error probabilities; High probability; Persistent errors; Probability p; Running time; Time algorithms; Random errors
Type
conference paper