https://scholars.lib.ntu.edu.tw/handle/123456789/624629
標題: | Approximate Minimum Selection with Unreliable Comparisons | 作者: | Leucci S CHIH-HUNG LIU |
關鍵字: | Approximate minimum selection; Independent errors; Unreliable comparisons | 公開日期: | 2022 | 卷: | 84 | 期: | 1 | 起(迄)頁: | 60-84 | 來源出版物: | Algorithmica | 摘要: | We consider the approximate minimum selection problem in presence of independent random comparison faults. This problem asks to select one of the smallest k elements in a linearly-ordered collection of n elements by only performing unreliable pairwise comparisons: whenever two elements are compared, there is a small probability that the wrong comparison outcome is observed. We design a randomized algorithm that solves this problem with a success probability of at least 1 - q for q∈(0,n-kn) and any k∈ [1 , n- 1] using O(nk⌈log1q⌉) comparisons in expectation (if k≥ n or q≥n-kn the problem becomes trivial). Then, we prove that the expected number of comparisons needed by any algorithm that succeeds with probability at least 1 - q must be Ω(nklog1q) whenever q is bounded away from n-kn, thus implying that the expected number of comparisons performed by our algorithm is asymptotically optimal in this range. Moreover, we show that the approximate minimum selection problem can be solved using O((nk+loglog1q)log1q) comparisons in the worst case, which is optimal when q is bounded away from n-kn and k=O(nloglog1q). © 2021, The Author(s). |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85118410305&doi=10.1007%2fs00453-021-00880-1&partnerID=40&md5=658671d8b156e2c4f3b21a58e5fe23ee https://scholars.lib.ntu.edu.tw/handle/123456789/624629 |
ISSN: | 01784617 | DOI: | 10.1007/s00453-021-00880-1 | SDG/關鍵字: | Artificial intelligence; Approximate minimum selection; Asymptotically optimal; Comparison faults; Independent error; K elements; Pair-wise comparison; Randomized Algorithms; Selection problems; Unreliable comparison; Probability |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。