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 nearlysorted permutation by performing a minimumcost 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 querycompetitive algorithms. The querycompetitiveness 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/2querycompetitive randomized algorithm; (ii) a 5/3querycompetitive deterministic algorithm if the dependency graph has no 2components after some preprocessing, which has querycompetitive 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 = {{QueryCompetitive Sorting with Uncertainty}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {7:17:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771177},
ISSN = {18688969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and JoostPieter Katoen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10951},
URN = {urn:nbn:de:0030drops109519},
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 
Seminar: 

44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) 
Issue Date: 

2019 
Date of publication: 

23.08.2019 