License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2018.36
URN: urn:nbn:de:0030-drops-85266
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8526/
Go to the corresponding LIPIcs Volume Portal

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

Optimal Dislocation with Persistent Errors in Subquadratic Time

pdf-format:
LIPIcs-STACS-2018-36.pdf (0.7 MB)

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

BibTeX - Entry

@InProceedings{geissmann_et_al:LIPIcs:2018:8526,
  author =	{Barbara Geissmann and Stefano Leucci and Chih-Hung Liu and Paolo Penna},
  title =	{{Optimal Dislocation with Persistent Errors in Subquadratic Time}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{36:1--36:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Rolf Niedermeier and Brigitte Vall{\'e}e},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8526},
  URN =		{urn:nbn:de:0030-drops-85266},
  doi =		{10.4230/LIPIcs.STACS.2018.36},
  annote =	{Keywords: sorting, recurrent comparison errors, maximum dislocation}
}

Keywords: sorting, recurrent comparison errors, maximum dislocation
Collection: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Issue Date: 2018
Date of publication: 27.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI