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.MFCS.2019.7
URN: urn:nbn:de:0030-drops-109519
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10951/
Go to the corresponding LIPIcs Volume Portal

Halldórsson, Magnús M. ; de Lima, Murilo Santos

Query-Competitive Sorting with Uncertainty

pdf-format:
LIPIcs-MFCS-2019-7.pdf (0.5 MB)

Abstract

We study the problem of sorting under incomplete information, when queries are used to resolve uncertainties. Each of n data items has an unknown value, which is known to lie in a given interval. We can pay a query cost to learn the actual value, and we may allow an error threshold in the sorting. The goal is to find a nearly-sorted permutation by performing a minimum-cost set of queries.
We show that an offline optimum query set can be found in polynomial time, and that both oblivious and adaptive problems have simple query-competitive algorithms. The query-competitiveness for the oblivious problem is n for uniform query costs, and unbounded for arbitrary costs; for the adaptive problem, the ratio is 2.
We then present a unified adaptive strategy for uniform query costs that yields: (i) a 3/2-query-competitive randomized algorithm; (ii) a 5/3-query-competitive deterministic algorithm if the dependency graph has no 2-components after some preprocessing, which has query-competitive ratio 3/2 + O(1/k) if the components obtained have size at least k; (iii) an exact algorithm if the intervals constitute a laminar family. The first two results have matching lower bounds, and we have a lower bound of 7/5 for large components.
We also show that the advice complexity of the adaptive problem is floor[n/2] if no error threshold is allowed, and ceil[n/3 * lg 3] for the general case.

BibTeX - Entry

@InProceedings{halldrsson_et_al:LIPIcs:2019:10951,
  author =	{Magn{\'u}s M. Halld{\'o}rsson and Murilo Santos de Lima},
  title =	{{Query-Competitive Sorting with Uncertainty}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10951},
  URN =		{urn:nbn:de:0030-drops-109519},
  doi =		{10.4230/LIPIcs.MFCS.2019.7},
  annote =	{Keywords: online algorithms, sorting, randomized algorithms, advice complexity, threshold tolerance graphs}
}

Keywords: online algorithms, sorting, randomized algorithms, advice complexity, threshold tolerance graphs
Collection: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 20.08.2019

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