Approximate Selection with Unreliable Comparisons in Optimal Expected Time

Autor: Huang, Shengyu, Liu, Chih-Hung, Rutschman, Daniel

Given $n$ elements, an integer $k$ and a parameter $\varepsilon$, we study to select an element with rank in $(k-n\varepsilon,k+n\varepsilon]$ using unreliable comparisons where the outcome of each comparison is incorrect independently with a constan

Externí odkaz: http://arxiv.org/abs/2205.01448

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Approximate Selection with Unreliable Comparisons in Optimal Expected Time

Autor: Huang, Shengyu, Liu, Chih-Hung, Rutschmann, Daniel

Publikováno v: Huang, S, Liu, C H & Rutschmann, D 2023, Approximate Selection with Unreliable Comparisons in Optimal Expected Time . in Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science : STACS 2023 ., 37, Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 254, 40th International Symposium on Theoretical Aspects of Computer Science, Hamburg, Germany, 07/03/2023 . https://doi.org/10.4230/LIPIcs.STACS.2023.37

Given n elements, an integer k ≤ n/2 and a parameter ε ≥ 1/n, we study the problem of selecting an element with rank in (k-nε, k+nε] using unreliable comparisons where the outcome of each comparison is incorrect independently with a constant e

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::90b6707132394904a188a5df6a6985b4

Quicksort with unreliable comparisons: a probabilistic analysis

Autor: Alonso, L., Chassaing, P., Gillet, F., Janson, S., Reingold, E. M., Schott, R.

We provide a probabilistic analysis of the output of Quicksort when comparisons can err.
Comment: 29 pages, 3 figures

Externí odkaz: http://arxiv.org/abs/math/0312437

Quicksort with unreliable comparisons: a probabilistic analysis

Autor: Svante Janson, René Schott, Edward M. Reingold, Florent Gillet, Laurent Alonso, Philippe Chassaing

Publikováno v: Combinatorics, Probability and Computing
Combinatorics, Probability and Computing, Cambridge University Press (CUP), 2004, 13 (4-5), pp.419-449. ⟨10.1017/S0963548304006297⟩
Combinatorics, Probability and Computing, 2004, 13 (4-5), pp.419-449. ⟨10.1017/S0963548304006297⟩

We provide a probabilistic analysis of the output of Quicksort when comparisons can err.
29 pages, 3 figures

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1a012ce3b4fea6f3c52a7aabc0b6ce47
http://arxiv.org/abs/math/0312437