License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.49
URN: urn:nbn:de:0030-drops-111706
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11170/
Geissmann, Barbara ;
Leucci, Stefano ;
Liu, Chih-Hung ;
Penna, Paolo
Optimal Sorting with Persistent Comparison Errors
Abstract
We consider the problem of sorting n elements in the case of persistent comparison errors. In this problem, each comparison between two elements can be wrong with some fixed (small) probability p, and comparisons cannot be repeated (Braverman and Mossel, SODA'08). 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 Omega(log n) and Omega(n), respectively, regardless of its running time.
In this paper, we present the first O(n log n)-time sorting algorithm that guarantees both O(log n) maximum dislocation and O(n) total dislocation with high probability. This settles the time complexity of this problem and shows that comparison errors do not increase its computational difficulty: a sequence with the best possible dislocation can be obtained in O(n log n) time and, even without comparison errors, Omega(n log n) time is necessary to guarantee such dislocation bounds.
In order to achieve this optimality result, we solve two sub-problems in the persistent error comparisons model, 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(log n) maximum dislocation in such a way that the dislocation of the resulting sequence will still be O(log n). 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.
BibTeX - Entry
@InProceedings{geissmann_et_al:LIPIcs:2019:11170,
author = {Barbara Geissmann and Stefano Leucci and Chih-Hung Liu and Paolo Penna},
title = {{Optimal Sorting with Persistent Comparison Errors}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {49:1--49:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-124-5},
ISSN = {1868-8969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11170},
URN = {urn:nbn:de:0030-drops-111706},
doi = {10.4230/LIPIcs.ESA.2019.49},
annote = {Keywords: approximate sorting, comparison errors, persistent errors}
}
|
Keywords: |
|
approximate sorting, comparison errors, persistent errors |
|
Collection: |
|
27th Annual European Symposium on Algorithms (ESA 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
06.09.2019 |
