2026-07-24T08:24:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10951 2024-03-06T10:46:54Z ddc:004 open_access

Query-Competitive Sorting with Uncertainty Halldórsson, Magnús M. de Lima, Murilo Santos online algorithms sorting randomized algorithms advice complexity threshold tolerance graphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Magnús M. Halldórsson and Murilo Santos de Lima 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.7 urn:nbn:de:0030-drops-109519 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.7 eng https://creativecommons.org/licenses/by/3.0/legalcode