Document Open Access Logo

Sorting with Recurrent Comparison Errors

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

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.38.pdf
  • Filesize: 0.54 MB
  • 12 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. Sorting with Recurrent Comparison Errors. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 38:1-38:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.38

Abstract

We present a sorting algorithm for the case of recurrent random comparison errors. The algorithm essentially achieves simultaneously good properties of previous algorithms for sorting n distinct elements in this model. In particular, it runs in O(n^2) time, the maximum dislocation of the elements in the output is O(log n), while the total dislocation is O(n). These guarantees are the best possible since we prove that even randomized algorithms cannot achieve o(log n) maximum dislocation with high probability, or o(n) total dislocation in expectation, regardless of their
running time.

Subject Classification

Keywords
  • sorting
  • recurrent comparison error
  • maximum and total dislocation

Metrics

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

References

  1. 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
  2. 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.
  3. Ferdinando Cicalese. Fault-Tolerant Search Algorithms - Reliable Computation with Unreliable Information. Monographs in Theoretical Computer Science. An EATCS Series. Springer, 2013. Google Scholar
  4. Don Coppersmith, Lisa K. Fleischer, and Atri Rurda. Ordering by weighted number of wins gives a good ranking for weighted tournaments. ACM Trans. Algorithms, 6(3):55:1-55:13, July 2010. URL: http://dx.doi.org/10.1145/1798596.1798608.
  5. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3. ed.). MIT Press, 2009. Google Scholar
  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 Journal on Computing, 23(5):1001-1018, 1994. URL: http://dx.doi.org/10.1137/S0097539791195877.
  8. Tomáš Gavenčiak, Barbara Geissmann, and Johannes Lengler. Sorting by swaps with noisy comparisons. In To appear in: Proceedings of the Genetic and Evolutionary Computation Conference 2016, GECCO '17, 2017. Google Scholar
  9. B. Geissmann and P. Penna. Sort well with energy-constrained comparisons. ArXiv e-prints, October 2016. URL: http://arxiv.org/abs/1610.09223.
  10. Petros Hadjicostas and KB Lakshmanan. Recursive merge sort with erroneous comparisons. Discrete Applied Mathematics, 159(14):1398-1417, 2011. Google Scholar
  11. Richard M. Karp and Robert Kleinberg. Noisy binary search and its applications. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 881-890, 2007. 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. Michael Mitzenmacher and Eli Upfal. Probability and computing - randomized algorithms and probabilistic analysis. Cambridge University Press, 2005. Google Scholar
  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. R. L. Graham Persi Diaconis. Spearman’s footrule as a measure of disarray. Journal of the Royal Statistical Society. Series B (Methodological), 39(2):262-268, 1977. 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