Document Open Access Logo

Optimal Dislocation with Persistent Errors in Subquadratic Time

Authors Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, Paolo Penna

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.36.pdf
  • Filesize: 0.66 MB
  • 13 pages

Document Identifiers

Author Details

Barbara Geissmann
Stefano Leucci
Chih-Hung Liu
Paolo Penna

Cite As Get BibTex

Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. Optimal Dislocation with Persistent Errors in Subquadratic Time. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 36:1-36:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.36

Abstract

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).

Subject Classification

Keywords
  • sorting
  • recurrent comparison errors
  • maximum dislocation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, and Jelani Nelson. Sorting and selection with imprecise comparisons. ACM Transactions on Algorithms, 12(2):19, 2016. Google Scholar
  2. Laurent Alonso, Philippe Chassaing, Florent Gillet, Svante Janson, Edward M Reingold, and René Schott. Quicksort with unreliable comparisons: a probabilistic analysis. Combinatorics, Probability and Computing, 13(4-5):419-449, 2004. Google Scholar
  3. Mark Braverman and Elchanan Mossel. Noisy Sorting Without Resampling. In Proceedings of the 19th Annual Symposium on Discrete Algorithms, pages 268-276, 2008. URL: http://arxiv.org/abs/0707.1051.
  4. Ferdinando Cicalese. Fault-Tolerant Search Algorithms - Reliable Computation with Unreliable Information. Monographs in Theoretical Computer Science. An EATCS Series. Springer, 2013. Google Scholar
  5. Don Coppersmith, Lisa Fleischer, and Atri Rudra. Ordering by weighted number of wins gives a good ranking for weighted tournaments. ACM Trans. Algorithms, 6(3):55:1-55:13, 2010. URL: http://dx.doi.org/10.1145/1798596.1798608.
  6. Peter Damaschke. The solution space of sorting with recurring comparison faults. In Combinatorial Algorithms - 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings, pages 397-408, 2016. Google Scholar
  7. Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal. Computing with noisy information. SIAM J. Comput., 23(5):1001-1018, 1994. URL: http://dx.doi.org/10.1137/S0097539791195877.
  8. Tomas Gavenciak, Barbara Geissmann, and Johannes Lengler. Sorting by swaps with noisy comparisons. In Peter A. N. Bosman, editor, Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2017, Berlin, Germany, July 15-19, 2017, pages 1375-1382. ACM, 2017. URL: http://dx.doi.org/10.1145/3071178.3071242.
  9. Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. Sorting with recurrent comparison errors. Proc of ISAAC 2017, 2017. To appear. And ArXiv e-prints arXiv:1709.07249, 2017. Google Scholar
  10. Barbara Geissmann and Paolo Penna. Sort well with energy-constrained comparisons. ArXiv e-prints arXiv:1610.09223, 2016. Google Scholar
  11. Petros Hadjicostas and KB Lakshmanan. Recursive merge sort with erroneous comparisons. Discrete Applied Mathematics, 159(14):1398-1417, 2011. Google Scholar
  12. Rolf Klein, Rainer Penninger, Christian Sohler, and David P. Woodruff. Tolerant Algorithms. In Proceedings of the19th Annual European Symposium on Algorithm, pages 736 - -747, 2011. Google Scholar
  13. Donald Ervin Knuth. The art of computer programming, Volume II: Seminumerical Algorithms, 3rd Edition. Addison-Wesley, 1998. URL: http://www.worldcat.org/oclc/312898417.
  14. Andrzej Pelc. Searching games with errors - fifty years of coping with liars. Theor. Comput. Sci., 270(1-2):71-109, 2002. Google Scholar
  15. Matthew Skala. Hypergeometric tail inequalities: ending the insanity. ArXiv e-prints arXiv:1311.5939, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact