We study the problem of sorting N elements in the presence of persistent errors in comparisons: In this classical model, each comparison between two elements is wrong independently with some probability up to p, but repeating the same comparison gives always the same result. In this model, it is impossible to reliably compute a perfectly sorted permutation of the input elements. Rather, the quality of a sorting algorithm is often evaluated w.r.t. the maximum dislocation of the sequences it computes, namely, the maximum absolute difference between the position of an element in the returned sequence and the position of the same element in the perfectly sorted sequence. The best known algorithms for this problem have running time O(N2) and achieve, w.h.p., an optimal maximum dislocation of O(log N) for constant error probability p. Note that no algorithm can achieve maximum dislocation o(log N) w.h.p., 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 it guarantees O(log N) maximum dislocation with high probability for any p ≤ 1/16.

### Optimal Dislocation with Persistent Errors in Subquadratic Time

#### Abstract

We study the problem of sorting N elements in the presence of persistent errors in comparisons: In this classical model, each comparison between two elements is wrong independently with some probability up to p, but repeating the same comparison gives always the same result. In this model, it is impossible to reliably compute a perfectly sorted permutation of the input elements. Rather, the quality of a sorting algorithm is often evaluated w.r.t. the maximum dislocation of the sequences it computes, namely, the maximum absolute difference between the position of an element in the returned sequence and the position of the same element in the perfectly sorted sequence. The best known algorithms for this problem have running time O(N2) and achieve, w.h.p., an optimal maximum dislocation of O(log N) for constant error probability p. Note that no algorithm can achieve maximum dislocation o(log N) w.h.p., 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 it guarantees O(log N) maximum dislocation with high probability for any p ≤ 1/16.
##### Scheda breve Scheda completa Scheda completa (DC)
2020
File in questo prodotto:
File
Geissmann2020_Article_OptimalDislocationWithPersiste.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: Documento in Versione Editoriale
Licenza: Creative commons
Dimensione 742.94 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11697/147820`
• ND
• 6
• 2