Metadata only
Date
2018-04-20Type
- Report
ETH Bibliography
yes
Altmetrics
Abstract
We consider the problem of sorting n elements in the case of persistent comparison errors. In this model (Braverman and Mossel, SODA'08), each comparison between two elements can be wrong with some fixed (small) probability p, and comparisons cannot be repeated. Sorting perfectly in this model is impossible, and the objective is to minimize the dislocation of each element in the output sequence, that is, the difference between its true rank and its position. Existing lower bounds for this problem show that no algorithm can guarantee, with high probability, maximum dislocation and total dislocation better than Ω(logn) and Ω(n), respectively, regardless of its running time. In this paper, we present the first \emph{O(nlogn)-time} sorting algorithm that guarantees both \emph{O(logn) maximum dislocation} and \emph{O(n) total dislocation} with high probability. Besides improving over the previous state-of-the art algorithms -- the best known algorithm had running time Õ (n3/2) -- our result indicates that comparison errors do not make the problem computationally more difficult: a sequence with the best possible dislocation can be obtained in O(nlogn) time and, even without comparison errors, Ω(nlogn) time is necessary to guarantee such dislocation bounds. In order to achieve this optimal result, we solve two sub-problems, and the respective methods have their own merits for further application. One is how to locate a position in which to insert an element in an almost-sorted sequence having O(logn) maximum dislocation in such a way that the dislocation of the resulting sequence will still be O(logn). The other is how to simultaneously insert m elements into an almost sorted sequence of m different elements, such that the resulting sequence of 2m elements remains almost sorted. Show more
Publication status
publishedExternal links
Journal / series
arXivPages / Article No.
Publisher
Cornell UniversityOrganisational unit
03340 - Widmayer, Peter / Widmayer, Peter
Funding
165524 - Energy-Tunable Combinatorial Algorithms (SNF)
More
Show all metadata
ETH Bibliography
yes
Altmetrics