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.2017.26
URN: urn:nbn:de:0030-drops-70077
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7007/
Go to the corresponding LIPIcs Volume Portal

Disser, Yann ; Kratsch, Stefan

Robust and Adaptive Search

pdf-format:
LIPIcs-STACS-2017-26.pdf (0.5 MB)

Abstract

Binary search finds a given element in a sorted array with an optimal number of log n queries. However, binary search fails even when the array is only slightly disordered or access to its elements is subject to errors. We study the worst-case query complexity of search algorithms that are robust to imprecise queries and that adapt to perturbations of the order of the elements. We give (almost) tight results for various parameters that quantify query errors and that measure array disorder. In particular, we exhibit settings where query complexities of log n + ck, (1+epsilon) log n + ck, and sqrt(cnk)+o(nk) are best-possible for parameter value k, any epsilon > 0, and constant c.

BibTeX - Entry

@InProceedings{disser_et_al:LIPIcs:2017:7007,
  author =	{Yann Disser and Stefan Kratsch},
  title =	{{Robust and Adaptive Search}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{26:1--26:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Heribert Vollmer and Brigitte ValleĢe},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7007},
  URN =		{urn:nbn:de:0030-drops-70077},
  doi =		{10.4230/LIPIcs.STACS.2017.26},
  annote =	{Keywords: searching, robustness, adaptive algorithms, memory faults, array disorder}
}

Keywords: searching, robustness, adaptive algorithms, memory faults, array disorder
Collection: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue Date: 2017
Date of publication: 06.03.2017

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