首页    期刊浏览 2024年12月01日 星期日
登录注册

文章基本信息

  • 标题:Optimal Dislocation with Persistent Errors in Subquadratic Time
  • 作者:Barbara Geissmann ; Stefano Leucci ; Chih-Hung Liu
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:96
  • 页码:36:1-36:13
  • DOI:10.4230/LIPIcs.STACS.2018.36
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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(N^2) 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 tilde{O}(N^{3/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).
  • 关键词:sorting; recurrent comparison errors; maximum dislocation
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有