https://scholars.lib.ntu.edu.tw/handle/123456789/624630
標題: | Optimal Dislocation with Persistent Errors in Subquadratic Time | 作者: | Geissmann B Leucci S Liu C.-H Penna P. CHIH-HUNG LIU |
關鍵字: | Maximum dislocation; Recurrent comparison errors; Sorting | 公開日期: | 2020 | 卷: | 64 | 期: | 3 | 起(迄)頁: | 508-521 | 來源出版物: | Theory of Computing Systems | 摘要: | 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. © 2019, Springer Science+Business Media, LLC, part of Springer Nature. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85076148014&doi=10.1007%2fs00224-019-09957-5&partnerID=40&md5=acf8d2d75fc536fd927f64d88755d9ae https://scholars.lib.ntu.edu.tw/handle/123456789/624630 |
ISSN: | 14324350 | DOI: | 10.1007/s00224-019-09957-5 | SDG/關鍵字: | Probability; Sorting; Best-known algorithms; Classical model; Error probabilities; High probability; Maximum absolute differences; Persistent errors; Sorting algorithm; Time algorithms; Errors |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。