https://scholars.lib.ntu.edu.tw/handle/123456789/624640
標題: | 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 | 公開日期: | 2018 | 卷: | 96 | 來源出版物: | Leibniz International Proceedings in Informatics, LIPIcs | 摘要: | 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. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85044523729&doi=10.4230%2fLIPIcs.STACS.2018.36&partnerID=40&md5=56c1484433a303e0d0b95162e3e33733 https://scholars.lib.ntu.edu.tw/handle/123456789/624640 |
ISSN: | 18688969 | DOI: | 10.4230/LIPIcs.STACS.2018.36 | SDG/關鍵字: | Probability; Sorting; Best-known algorithms; Classical model; Error probabilities; High probability; Persistent errors; Probability p; Running time; Time algorithms; Random errors |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。