University of Leicester
Browse
LIPIcs-MFCS-2019-7.pdf (528.42 kB)

Query-Competitive Sorting With Uncertainty

Download (528.42 kB)
conference contribution
posted on 2020-04-29, 13:39 authored by Magnus M Halldorsson, Murilo de Lima
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.

Funding

Partially supported by Icelandic Research Fund grant 174484-051.

History

Citation

44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Editors: Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen; Article No. 7; pp. 7:1–7:15

Source

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

Published in

LIPIcs : Leibniz International Proceedings in Informatics

Volume

138

Pagination

7:1 - 7:15 (15)

Publisher

Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik

issn

1868-8969

Copyright date

2019

Publisher version

https://leicester.figshare.com/institution/review#/requests/471291

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC